C++ O(N) with explanation && example
Handler the letter by its type one by one starting with the largest one (due to sorting), for example, \'9\' first, then \'8\', ...\n\nThe reason is based on an
Handler the letter by its type one by one starting with the largest one (due to sorting), for example, \'9\' first, then \'8\', ...\n\nThe reason is based on an observation: after sorting the substring, the letters with the same name still maintain the relateive positions. \n\nLet take \'9\' as an example,\n\nif there are 3 \'9\'s in s, and also 3 in t  (if not the same, return false);\nthen the id (index) of the 1st \'9\' in s should be <= the id of the 1st \'9\' in t (if not, return false,  **why?  since there is no way the id of the 1st \'9\' in s becomes smaller due to sorting (or there is no bigger letter than \'9\'**));\nthen the id of the 2nd \'9\' in s should be <= the id of the 2nd \'9\' in t (if not, return false);\n...\n\nif all satisfy, then we can remove all \'9\' from s and t, then recursively run the same procedure but with a smaller size.\n\nafter removing all \'9\'s, the next one is \'8\', ...\n\nif all can be removed, return true.\n\nMore details can be found here:\nhttps://algorithm-notes-allinone.blogspot.com/2020/09/leetcode-1585-check-if-string-is.html\n\nSee the code below:\n\n```\nclass Solution {\npublic:\n    bool isTransformable(string s, string t) {\n        string s1 = s, t1 = t;\n        for(char c=\'9\'; c>=\'0\'; --c) {\n            vector<int> ids1, ids2;\n            for(int i=0; i<s1.size(); ++i) {\n                if(s1[i] == c) ids1.push_back(i);\n                if(t1[i] == c) ids2.push_back(i);\n            }\n            if((int)ids1.size() != (int)ids2.size()) return false;\n            for(int i=0; i<ids1.size(); ++i) {\n                if(ids1[i] > ids2[i]) return false;\n            }\n            string s2 = "", t2 = "";\n            for(auto &a : s1) {\n                if(a < c) s2.push_back(a);\n            }\n            for(auto &a : t1) {\n                if(a < c) t2.push_back(a);\n            }\n            s1 = s2;\n            t1 = t2;\n         //   cout<<s1<<" "<<t1<<endl;\n        }\n        return true;\n    }\n};\n```
[]