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)
Top comments (0)