What is the main algorithm used in Smallest String With Swaps?

The problem can be solved using union-find, DFS, or BFS to identify connected components and then sorting the characters within each component.

How do swaps in Smallest String With Swaps help minimize the string?

By swapping characters that are part of the same connected component, you can sort them lexicographically to obtain the smallest possible string.

What is the time complexity of the solution for Smallest String With Swaps?

The time complexity is O(N * α(N)) for union-find, or O(N + M) for DFS/BFS, where N is the number of characters and M is the number of pairs.

Can Smallest String With Swaps be solved without sorting?

No, sorting is essential to ensure the characters within each connected component are arranged lexicographically.

What is the graph theory application in Smallest String With Swaps?

The problem can be viewed as a graph where indices are nodes, and pairs are edges. The goal is to find connected components and sort the characters within them.

#1202

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

交换字符串中的元素

给你一个字符串 s ，以及该字符串中的一些「索引对」数组 pairs ，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。你可以任意多次交换在 pairs 中任意一对索引处的字符。返回在经过若干次交换后， s 可以变成的按字典序最小的字符串。示例 1: …

数组哈希表字符串深度优先搜索广度优先搜索

题目描述

给你一个字符串 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 中只含有小写英文字母

lightbulb

解题思路

方法一：并查集

我们注意到，索引对具有传递性，即如果 $a$ 与 $b$ 可交换，而 $b$ 与 $c$ 可交换，那么 $a$ 与 $c$ 也可交换。因此，我们可以考虑使用并查集维护这些索引对的连通性，将属于同一个连通分量的字符按照字典序排序。

最后，遍历字符串，对于当前位置的字符，我们将其替换为该连通分量中最小的字符，然后从该连通分量中取出该字符，继续遍历字符串即可。

时间复杂度 $O(n \times \log n + m \times \alpha(m))$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别为字符串的长度和索引对的数量，而 $\alpha$ 为阿克曼函数的反函数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        n = len(s)
        p = list(range(n))
        for a, b in pairs:
            p[find(a)] = find(b)
        d = defaultdict(list)
        for i, c in enumerate(s):
            d[find(i)].append(c)
        for i in d.keys():
            d[i].sort(reverse=True)
        return "".join(d[find(i)].pop() for i in range(n))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of graph theory, particularly connected components.
question_mark
Pay attention to how the candidate handles sorting within each connected component.
question_mark
Check for optimization in the approach, especially in handling large inputs.

warning

常见陷阱

外企场景

error
Forgetting to sort the characters within each connected component.
error
Failing to recognize that the problem is essentially about identifying connected components in a graph.
error
Not handling edge cases like no pairs or the minimum string length.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the swaps are limited to certain indices?
arrow_right_alt
How would you optimize this problem for larger strings or more pairs?
arrow_right_alt
Can this problem be solved with dynamic programming instead of graph traversal?

help

常见问题

外企场景

继续练习

#721 账户合并 #839 相似字符串组 #959 由斜杠划分区域