1202. Smallest String With Swaps

Medium

---

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.

Example 1:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

Example 2:

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"

Example 3:

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination: 
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"

Constraints:

• 1 <= s.length <= 10^5

• 0 <= pairs.length <= 10^5

• 0 <= pairs[i][0], pairs[i][1] < s.length

• s only contains lower case English letters.

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        # Seems like a graph where together connected components needs to be 
        # sorted. Example 0 -> 1 -> 2 if these indices are connected then we need to simple sort these
        d = defaultdict(list)
        for source, destination in pairs:
            d[source].append(destination)
            d[destination].append(source)
        self.d = d
        visited = [False]*(len(s))
        self.visited = visited
        result = ['']*len(s)
        for vertex in range(len(s)):
            if not self.visited[vertex]:
                chars = []
                indices = []
                self.DFS(s, vertex, chars, indices)
                chars.sort()
                indices.sort()
                for index in range(len(chars)):
                    result[indices[index]] = chars[index]
        return ''.join(result)
    
    def DFS(self, s, vertex, chars, indices):
        chars.append(s[vertex])
        indices.append(vertex)
        self.visited[vertex] = True
        for adj in self.d[vertex]:
            if not self.visited[adj]:
                self.DFS(s, adj, chars, indices)