C++ Easy Explained Understandable Fast
Approach\nWe can shift each element that is larger down the array to \nit\'s correct spot as long as there\'s nothing smaller than\nit blocking the way.\n\n Now
# Approach\nWe can shift each element that is larger down the array to \nit\'s correct spot as long as there\'s nothing smaller than\nit blocking the way.\n\n Now, we can consider this by CHARACTER.\nIf you\'re struggling with a string question, it\'s helpful\nto think what sort of interest loops you can come up with\nregarding the chars, even if it\'s 26 or 10 (in this case).\nAllows for a lot of flexible solutions that are also fast.\n\nHowever, we cannot just go to each char in t, iterate until\nyou find it in s, and assign it. We have to do everything\nat the same time for the algo to be O(n). So as we are iterating\nthrough t, we are also iterating through s. \n\nThe trick here is to use a queue for every single char in s, \nit\'s q[10] = idx. Thus, it will contain every char in order, and\nif you are trying to move \'4\' at index 5 to it\'s correct spot, you\ncan check for \'0\',\'1\',\'2\',\'3\' if there are any indexes that come \nearlier than 5 (then it will be impossible, as you will never be\nable to shift \'4\' below this char. \n\nSo now the algorithm goes: For each char in t...\nyou can pop it off the q and consider it assigned - but first check\nall chars under the t char, and see if there are any unassigned\nchars that come earlier than the current char -> if there is, it \nwill be impossible to move the t char below this char that is\nlarger and unassigned.\n\n# Code\n```\nclass Solution {\npublic:\n    int ct1[10], ct2[10];\n    bool isTransformable(string s, string t) {\n        int n = s.size();\n        queue<int> q[10];\n        for (int i = 0; i < n; i++) {\n            int ch1 = s[i]-\'0\', ch2 = t[i]-\'0\';\n            ct1[ch1]++; ct2[ch2]++;\n            q[ch1].push(i);\n        }\n        for (int i = 0; i < 10; i++) {\n            if (ct1[i] != ct2[i]) return false;\n        }\n        for (int i = 0; i < n; i++) {\n            int ch = t[i] - \'0\';\n            for (int j = 0; j < ch; j++) {\n                if (!q[j].empty() && q[j].front() < q[ch].front()) {\n                    return false;\n                }\n            }\n            q[ch].pop();\n        }\n        return true;\n    }\n};\n```
['C++']