One O(n) solution and I can't explain it by myself...
I can\'t explain why my code works... but the gut feeling in the contest is right.\n\nCheck the source string, for each digit, get the number of smaller digit i
I can\'t explain why my code works... but the gut feeling in the contest is right.\n\nCheck the source string, for each digit, get the number of smaller digit in following part.\nDo the same for target string.\n\nThen, for each digit, if the smaller-number in source < smaller-number in target, then this source can\'t be converted into target, because smaller number before the digit can\'t be sorted into following part.\n\n```\n class Solution {\npublic:\n    bool isTransformable(string s, string t) {\n        vector<int> num(128);\n        for (int i = 0; i < s.size(); ++i) {\n            num[s[i]]++;\n            num[t[i]]--;\n        }\n        for (int i = \'0\'; i <= \'9\'; ++i) {\n            if (num[i] != 0) {\n                return false;\n            }\n        }\n        \n        //cout << "f" << endl;\n        vector<vector<int>> target(10), source(10);\n        vector<int> tn(10), sn(10);\n        for (int i = s.size() - 1; i >= 0; --i) {\n            sn[s[i]-\'0\']++;\n            int sum = 0;\n            for (int j = 0; j+\'0\' < s[i]; ++j) {\n                sum += sn[j];\n            }\n            source[s[i]-\'0\'].push_back(sum);\n            \n            tn[t[i]-\'0\']++;\n            sum = 0;\n            for (int j = 0; j+\'0\' < t[i]; ++j) {\n                sum += tn[j];\n            }\n            target[t[i]-\'0\'].push_back(sum);\n        }\n        \n        for (int i = 1; i <= 9; ++i) {\n            for (int j = 0; j < source[i].size(); ++j) {\n                if (source[i][j] < target[i][j]) {\n                    return false;\n                }\n            }\n        }\n        \n        return true;\n    }\n};\n```
[]