Smallest String With Swaps

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.

SOLUTION:

from collections import defaultdict class Solution: def dfs(self, graph, node, visited): for j in graph[node]: if j not in visited: visited.add(j) self.dfs(graph, j, visited) def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str: op = list(s) graph = defaultdict(list) for a, b in pairs: graph[a].append(b) graph[b].append(a) globalvisited = set() for x in graph: if x not in globalvisited: currvisited = {x} self.dfs(graph, x, currvisited) indexes = sorted(currvisited) indexes_asc = sorted(currvisited, key = lambda p: s[p]) n = len(indexes) for i in range(n): op[indexes[i]] = s[indexes_asc[i]] globalvisited.update(currvisited) return "".join(op)