1202. Smallest String With Swaps

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

c++

class Solution {
    int getParent(vector<int>& gr, int a) {
        return gr[a] == a ? a : gr[a] = getParent(gr, gr[a]);
    }
    void merge(vector<int>& gr, int a, int b) {
        int pa = getParent(gr,a);
        int pb = getParent(gr,b);
        gr[pa] = gr[pb] = min(pa,pb);
    }
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.length();
        vector<int> gr(n);
        for(int i = 0; i < n; i++) gr[i] = i;
        for(auto& p : pairs) {
            merge(gr,p[0],p[1]);
        }

        unordered_map<int, vector<char>> m;
        for(int i = 0; i < n; i++) {
            m[getParent(gr, i)].push_back(s[i]);
        }
        for(auto& [k, v]: m) {
            sort(v.begin(), v.end(), greater<char>());
        }

        for(int i = 0; i < n; i++) {
            s[i] = m[gr[i]].back();
            m[gr[i]].pop_back();
        }

        return s;
    }
};