<p>You are given a string <code>s</code>, and an array of pairs of indices in the string&nbsp;<code>pairs</code>&nbsp;where&nbsp;<code>pairs[i] =&nbsp;[a, b]</code>&nbsp;indicates 2 indices(0-indexed) of the string.</p>

<p>You can&nbsp;swap the characters at any pair of indices in the given&nbsp;<code>pairs</code>&nbsp;<strong>any number of times</strong>.</p>

<p>Return the&nbsp;lexicographically smallest string that <code>s</code>&nbsp;can be changed to after using the swaps.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;dcab&quot;, pairs = [[0,3],[1,2]]
<strong>Output:</strong> &quot;bacd&quot;
<strong>Explaination:</strong> 
Swap s[0] and s[3], s = &quot;bcad&quot;
Swap s[1] and s[2], s = &quot;bacd&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;dcab&quot;, pairs = [[0,3],[1,2],[0,2]]
<strong>Output:</strong> &quot;abcd&quot;
<strong>Explaination: </strong>
Swap s[0] and s[3], s = &quot;bcad&quot;
Swap s[0] and s[2], s = &quot;acbd&quot;
Swap s[1] and s[2], s = &quot;abcd&quot;</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cba&quot;, pairs = [[0,1],[1,2]]
<strong>Output:</strong> &quot;abc&quot;
<strong>Explaination: </strong>
Swap s[0] and s[1], s = &quot;bca&quot;
Swap s[1] and s[2], s = &quot;bac&quot;
Swap s[0] and s[1], s = &quot;abc&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10^5</code></li>
	<li><code>0 &lt;= pairs.length &lt;= 10^5</code></li>
	<li><code>0 &lt;= pairs[i][0], pairs[i][1] &lt;&nbsp;s.length</code></li>
	<li><code>s</code>&nbsp;only contains lower case English letters.</li>
</ul>

/*
[0, 2] [2, 4] [0, 5]
zybvxf
bfz

if we can group indices which are kind of connected, and then can sort the characters on those indices and if 
we do this for every group we will get the lexicographically smallest string.
*/

struct DSU {
    vector<int> par, rank;
    
    DSU(int n) {
        par = vector<int>(n);
        rank = vector<int>(n);
        for (int i = 0; i < n; ++i) {
            par[i] = i, rank[i] = 1;
        }
    }
    
    int findPar(int u) {
        if (par[u] == u) {
            return u;
        }
        return par[u] = findPar(par[u]);
    }
    
    void doUnion(int u, int v) {
        u = findPar(u), v = findPar(v);
        if (rank[u] > rank[v]) {
            par[v] = u;
        }
        else if (rank[v] > rank[u]) {
            par[u] = v;
        }
        else {
            par[u] = v;
            rank[v] += 1;
        }
    }
};

class Solution {
public:
    
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        DSU dsu(n);
        
        for (auto &pair: pairs) {
            int u = pair[0], v = pair[1];
            if (dsu.findPar(u) != dsu.findPar(v)) {
                dsu.doUnion(u, v);
            }
        }
        
        unordered_map<int, string> indGroup;
        for (int i = 0; i < n; ++i) {
            indGroup[dsu.findPar(i)].push_back(s[i]);
        }
        for (auto &[parInd, charGroup] : indGroup) {
            sort(charGroup.begin(), charGroup.end(), greater<char>());
        }
        
        string resStr = "";
        for (int i = 0; i < n; ++i) {
            resStr.push_back(indGroup[dsu.findPar(i)].back());
            indGroup[dsu.findPar(i)].pop_back();
        }
        return resStr;
    }
};
50562