Quote: "Lower digit cannot move to the right of higher digit in s"
It is hard to explain the idea, but I instantly know the idea by reading this comment: https://leetcode.com/problems/check-if-string-is-transformable-with-subst
It is hard to explain the idea, but I instantly know the idea by reading this comment: https://leetcode.com/problems/check-if-string-is-transformable-with-substring-sort-operations/discuss/843917/C++JavaPython-O(n)/694292\n\n```\nclass Solution {\npublic:\n    bool isTransformable(string s, string t) {\n        array<deque<array<int, 10>>, 10> s_last_count{}, t_last_count{};\n        array<int, 10> s_curr_count{}, t_curr_count{};\n        for (int i = 0; i < s.size(); ++i) {\n            int s_ch_idx = s[i] - \'0\';\n            ++s_curr_count[s_ch_idx];\n            if (t_last_count[s_ch_idx].empty()) {\n                s_last_count[s_ch_idx].emplace_back(s_curr_count);\n            } else {\n                for (int j = 0; j < s_ch_idx; ++j) {\n                    if (t_last_count[s_ch_idx].front()[j] < s_curr_count[j]) {\n                        return false;\n                    }\n                }\n                t_last_count[s_ch_idx].pop_front();\n            }\n\n            int t_ch_idx = t[i] - \'0\';\n            ++t_curr_count[t_ch_idx];\n            if (s_last_count[t_ch_idx].empty()) {\n                t_last_count[t_ch_idx].emplace_back(t_curr_count);\n            } else {\n                for (int j = 0; j < t_ch_idx; ++j) {\n                    if (s_last_count[t_ch_idx].front()[j] > t_curr_count[j]) {\n                        return false;\n                    }\n                }\n                s_last_count[t_ch_idx].pop_front();\n            }\n        }\n\n        for (int i = 0; i < 10; i++) {\n            if (!s_last_count[i].empty() || !t_last_count[i].empty()) {\n                return false;\n            }\n        }\n\n        return true;\n    }\n};\n\n```
[]