Leetcode 1202: Smallest String With Swaps

https://leetcode.com/problems/smallest-string-with-swaps/description/

Notes:

The key to this question is to understand what it means!!!

After thinking for a while, it basically says that we can swap any letters at that two positions if they can be swapped. Then, there maybe more than 2 positions correlated. Since we can swap them unlimitedly, which means we can always reach the lexicographical order of the letters correlated.

Or, if the letters belongs to a group (which means correlated), then we just need to sort them directly, then place them back in order to the previous positions. So the key is to determine the groups.

To this problem, union-find algorithm is a good choice. Using this algorithm, we can easily determine how many groups in a graph.

For this question, we need to move one step more. We need to figure out for each group, what are the elements? It seems not easy, but actually it is.  After running the union-find, we have built the union-find map for all the elements. We just need to check the root of each element, then we can easily print out the elements of each group (the root of each group is unique).

For union-find, it is almost O(1) in time to get the root of each elements. So it is fast.

See the code below:

class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int len = s.size();
        vector<vector<int>> mp(len);
        vector<int> rs(len, 0);
        for(int i=0; i<len; ++i) rs[i] = i;
        for(auto &a : pairs) {
            int x = find(a[0], rs), y = find(a[1], rs);
            if(x != y) rs[y] = x;
        }
        for(int i=0; i<len; ++i) mp[find(i, rs)].push_back(i);
        for(auto &a : mp) {
            string ss = "";
            for(auto &b : a) ss.push_back(s[b]);
            sort(ss.begin(), ss.end());
            for(int i=0; i<a.size(); ++i) s[a[i]] = ss[i];
        }
        return s;
    }

private:
    int find(int x, vector<int> &rs) {
        if(rs[x] != x) rs[x] = find(rs[x], rs);
        return rs[x];
    }
};