title
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
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
uf = {i:i for i in range(len(s))}
def find(x):
if uf[x] != x:
uf[x] = find(uf[x])
return uf[x]
def union(a, b):
uf[find(a)] = find(b)
https://www.jiuzhang.com/solution/
for a, b in pairs:
union(a, b)
root_elements = {}
for i in range(len(s)):
root_i = find(i)
if root_i not in root_elements:
root_elements[root_i] = set()
root_elements[root_i].add(i)
s = list(s)
for root, eles in root_elements.items():
slist = [s[i] for i in eles]
sort_slist = sorted(slist)
print("sort_slist: ", sort_slist)
j = 0
for i in sorted(eles):
s[i] = sort_slist[j]
j += 1
print("s: ", s)
return "".join(s)