<jupyter_start><jupyter_text>给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。    你可以 任意多次交换 在 pairs 中任意一对索引处的字符。    返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。示例 1:    输入：s = "dcab", pairs = [[0,3],[1,2]]    输出："bacd"    解释：         交换 s[0] 和 s[3], s = "bcad"        交换 s[1] 和 s[2], s = "bacd"示例 2：    输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]    输出："abcd"    解释：        交换 s[0] 和 s[3], s = "bcad"        交换 s[0] 和 s[2], s = "acbd"        交换 s[1] 和 s[2], s = "abcd"示例 3：    输入：s = "cba", pairs = [[0,1],[1,2]]    输出："abc"    解释：        交换 s[0] 和 s[1], s = "bca"        交换 s[1] 和 s[2], s = "bac"        交换 s[0] 和 s[1], s = "abc"提示：    1 <= s.length <= 10^5    0 <= pairs.length <= 10^5    0 <= pairs[i][0], pairs[i][1] < s.length    s 中只含有小写英文字母<jupyter_code>from collections import defaultdict

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs) -> str:
        def find(x):
            if father[x] != x:
                father[x] = find(father[x])
            return father[x]
        
        def union(a, b):
            a, b = find(a), find(b)
            if a > b:
                father[a] = b
            else:
                father[b] = a
        # 将 pairs 中出现的两个点对应的 s idx 做一个 union
        N = len(s)
        father = [i for i in range(N)]
        for i, j in pairs:
            if father[i] != father[j]:
                union(i, j)
        
        union_dict = defaultdict(list)
        for i in range(N):
            union_dict[father[i]].append(i)
        
        s = list(s)
        for k, v in union_dict.items():
            temp = ''
            for i in v:
                temp += s[i]
            temp = sorted(temp)
            for i, j in enumerate(v):
                s[j] = temp[i]
        return ''.join(s)
from collections import defaultdict

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs) -> str:
        def find(x):
            if father[x] != x:
                father[x] = find(father[x])
            return father[x]
        
        def union(a, b):
            a, b = find(a), find(b)
            if a > b:
                father[a] = b
            else:
                father[b] = a
        
        # 将 pairs 中出现的两个点对应的 s idx 做一个 union
        N = len(s)
        father = [i for i in range(N)]
        for i, j in pairs:
            union(i, j)
        
        print(father)
        memo = defaultdict(list)
        for i, v in enumerate(father):
            memo[find(v)].append(s[i])
        for k in memo:
            memo[k].sort(reverse=True)
        res = []
        for i in range(N):
            res.append(memo[find(i)].pop())
        return ''.join(res)
solution = Solution()
solution.smallestStringWithSwaps("dcab", [[0,3],[1,2],[0,2]])<jupyter_output>[0, 0, 1, 0]
{'fraction_non_alphanumeric': 0.1528478731074261, 'fraction_numerical': 0.019826964671953856, 'mean_word_length': 1.5576036866359446, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '184792', 'license': 'Apache-2.0', 'n_tokens_mistral': 1147, 'n_tokens_neox': 1164, 'n_words': 276, 'path': 'Union Fold/1116/1202. Smallest String With Swaps.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '2774'}