Explanation and thought process for beginners
Intuition\nWe can try and match the strings from left and right character by character. We can use sorting to bring the desired character to the left and iterat
# Intuition\nWe can try and match the strings from left and right character by character. We can use sorting to bring the desired character to the left and iterate through the entire string. Seems basic but a good place to start.\n\n# Approach\nThe problem with sorting subarrays is that we have multiple ways of so, for example to bring `1` to the front for `321` we can sort the entire array into `123` or use multiple sorts `321 -> 312 -> 132`. Which one do we choose?\n\nThe second way is better since we can easily turn `132` to `123` with another swap. In fact, the second way is bubble sort. It is easy to see that by using only single swaps, we can simulate all possibilities of sortings while larger sorts will result in some possibilities being lost (`123` cannot turn into `312`). Another way of justifying this is that using consequtive single swaps will not disturb the order of other elements, therefore leaving us the greatest amount of flexibility (since once a smaller element is sorted with a larger element, it can no longer go to the right of that larger element). \n\nHow can we be sure that we can bring the desired element to the left? Well, as long as there is not a smaller element between `[0...i]` where `i` is the index of the desired element, we are fine. \n\nThis gives us a basic idea of our algorithm: for every character `c` in `t`, we want to find the same character in `s`, check that there is no character smaller than `c` and is also to the left of `c`, swap `c` with its left neighbor all the way until it is to the front, cut off the leftmost character in both stringw, repeat until both strings are empty. \n\nObviously, blindly following the algorithm will be too time exhausting, we can apply a few optimizations and make the algorithm a lot more efficient.\n\n# Complexity\n- Time complexity: `O(n)`\n\n- Space complexity: `O(n)`\n\n# Code\n```\nclass Solution {\npublic:\n    bool isTransformable(string s, string t) {\n        vector<vector<int>> pos(10);\n        for (int i = s.size() - 1; i >= 0; i--) pos[s[i] - \'0\'].push_back(i);\n        \n        for (int i = 0; i < t.size(); i++) {\n            int d = t[i] - \'0\';\n            \n            if (!pos[d].size()) return false;\n            for (int j = 0; j < d; j++) {\n                if (pos[j].size() && pos[j].back() < pos[d].back()) return false;\n            }\n            \n            pos[d].pop_back();\n        }\n        \n        return true;\n    }\n};\n```
['C++']