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


### Solution 1 - DFS
class Solution(object):
    def smallestStringWithSwaps(self, s, pairs):
        """
        :type s: str
        :type pairs: List[List[int]]
        :rtype: str
        """
        graph = defaultdict(list)
        s = list(s)
        for u, v in pairs:
            graph[u].append(v)
            graph[v].append(u)
        
        seen = set()

        def dfs(i, chars, indices):
            if i in seen:
                return
            
            seen.add(i)
            chars.append(s[i])
            indices.append(i)

            for neighbor in graph[i]:
                dfs(neighbor, chars, indices)
            
        for i in range(len(s)):
            if i in seen:
                continue
            
            chars = []
            indices = []
            dfs(i, chars, indices)
            chars.sort()
            indices.sort()
            for c, i in zip(chars, indices):
                s[i] = c
        
        return ''.join(s)

### Solution 2 - Union Find

# class Solution(object):
#     def smallestStringWithSwaps(self, s, pairs):
#         """
#         :type s: str
#         :type pairs: List[List[int]]
#         :rtype: str
#         """
#         from collections import defaultdict

#         s = list(s)
#         nodes = [i for i in range(len(s))]
#         size = [1 for i in range(len(s))]

#         def find(x):
#             if x == nodes[x]:
#                 return x
#             nodes[x] = find(nodes[x])
#             return nodes[x]

#         def union(x, y):
#             rootx = find(x)
#             rooty = find(y)
#             if rootx != rooty:
#                 nodes[rooty] = rootx

#         for e1, e2 in pairs:
#             union(e1, e2)

#         rootToComponent = defaultdict(list)

#         for i in range(len(s)):
#             root = find(i)
#             rootToComponent[root].append(i)

#         for k, indices in rootToComponent.items():
#             chars = []
#             for i in indices:
#                 chars.append(s[i])
#             chars = sorted(chars)

#             for c, i in zip(chars, indices):
#                 s[i] = c

#         return "".join(s)
59293