Problem statement

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

Solution

We just need to find connected components: we can do it either with dfs or with union find. Also we need to return the lexicographically smallest string, so we need to sort values inside each connected component.

Complexity

for this dfs solution complexity is O(n log n + E), where n is length of s and E is number of connections.

Code

class Solution:
    def smallestStringWithSwaps(self, s, pairs):
        visited, ans, graph = set(), {}, defaultdict(list)
        comps, ind, n = defaultdict(list), 0, len(s)
        for x, y in pairs:
            graph[x].append(y)
            graph[y].append(x)
        
        def dfs(node, i):
            visited.add(node)
            comps[i].append(node)
            for neib in graph[node]:
                if neib in visited: continue
                dfs(neib, i)
                
        for i in range(n):
            if i not in visited:
                dfs(i, ind)
                ind += 1
                
        for comp in comps.values():
            for i, l in zip(sorted(comp), sorted(s[t] for t in comp)):
                ans[i] = l
            
        return "".join(ans[i] for i in range(n))