<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>

class DSQuickUnionByRank: 

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [1]* n #Refers to the height of each vertex 
        self.count = n

    def findRoot(self, vert): 
        if vert == self.parent[vert]:
            return vert
        self.parent[vert] = self.findRoot(self.parent[vert])
        return self.parent[vert]

    def doUnion(self, i , j):
        rooti, rootj = self.findRoot(i), self.findRoot(j)
        if rooti != rootj: 
            if self.rank[rooti] > self.rank[rootj]: 
                self.parent[rootj] = self.parent[rooti]
            elif self.rank[rooti] < self.rank[rootj]: 
                self.parent[rooti] = self.parent[rootj]
            else: 
                self.parent[rooti] = self.parent[rootj]
                self.rank[rootj] += 1 
            self.count -= 1

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        n = len(s)
        obj = DSQuickUnionByRank(n)

        for pair in pairs: 
            [row, col] = pair
            obj.doUnion(row, col)

        if obj.count == n: return s

        listRoot = [obj.findRoot(vert) for vert in range(n)]
        setRoot = set(listRoot)
        listRoot = [(vert,obj.findRoot(vert)) for vert in range(n)]
        out = ''
        dictRoot = {}

        for letter in range(n): 
            if listRoot[letter][1] in dictRoot:
                dictRoot[listRoot[letter][1]][0] += 1
                dictRoot[listRoot[letter][1]][1].append(s[letter])
            else:
                dictRoot[listRoot[letter][1]] = [0, [s[letter]], 0]

        print(dictRoot)

        for key in dictRoot.keys():
            dictRoot[key][1].sort()

        for elm in listRoot: 
            (letter, root) = elm
            out = out + dictRoot[root][1][dictRoot[root][2]]
            dictRoot[root][2] += 1

        print(out)

        return out


        
536