Leetcode 1585: Check If String Is Transformable With Substring Sort Operations

 https://leetcode.com/problems/check-if-string-is-transformable-with-substring-sort-operations/description/

Notes:

There are only 10 types of letters, so one way is that we can handle them one by one.

One of the key observations for sorting sub-string (or any type of ascending sorting): the id of the largest element will no way get smaller (or the position cannot be moved forward in an ascending sort).

Based on this, we can just start with the largest letter, then the second largest one, ... until all done.

Let take '9' as an example, 

1): say there are 3 '9's in s and also 3 in t (if not, return false directly);

2): then the id 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'));

3): then the id of the 2nd '9' in s should be <= the id of the 2nd '9' in t (if not, return false);

...

If all satisfy, then we can remove all '9' from s and t, then recursively run the same procedure but with a smaller size.

After removing all '9's, the next one is '8', ...

If all can be removed, return true.

[update: 2024/11/27] 

As commented @Kaisar below, there is a case ("891", "198") cannot pass.

We can just apply the same logic but with the reversed order: starting from '0', then the id of the smallest element will no way get larger.

When the results from both directions are true, return true. 

See the code below:

class Solution {
public:
    bool isTransformable(string s, string t) {
        string s1 = s, t1 = t;
        // check ids of elements from largest to smallest;
        for(char c='9'; c>='0'; --c) {
            vector<int> ids1, ids2;
            for(int i=0; i<s1.size(); ++i) {
                if(s1[i] == c) ids1.push_back(i);
                if(t1[i] == c) ids2.push_back(i);
            }
            if((int)ids1.size() != (int)ids2.size()) return false;
            for(int i=0; i<ids1.size(); ++i) {
                if(ids1[i] > ids2[i]) return false;
            }
            string s2 = "", t2 = "";
            for(auto &a : s1) {
                if(a < c) s2.push_back(a);
            }
            for(auto &a : t1) {
                if(a < c) t2.push_back(a);
            }
            s1 = s2;
            t1 = t2;
        }
        // check ids of elements from smallest to the largest;
        s1 = s, t1 = t;
        for(char c='0'; c<='9'; ++c) {
            vector<int> ids1, ids2;
            for(int i=0; i<s1.size(); ++i) {
                if(s1[i] == c) ids1.push_back(i);
                if(t1[i] == c) ids2.push_back(i);
            }
            if((int)ids1.size() != (int)ids2.size()) return false;
            for(int i=0; i<ids1.size(); ++i) {
                if(ids1[i] < ids2[i]) return false;
            }
            string s2 = "", t2 = "";
            for(auto &a : s1) {
                if(a > c) s2.push_back(a);
            }
            for(auto &a : t1) {
                if(a > c) t2.push_back(a);
            }
            s1 = s2;
            t1 = t2;
        }
        return true;
    }
};