题目描述

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.

样例

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"

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"

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"

限制

• 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.

算法

1. 枚举索引对，利用并查集生成连通子图。
2. 在同一个连通子图内，字符可以随意排列。此时，只需将每个连通子图内的字符集倒序排列，然后将每个连通子图内的字符集从后往前放回对应的位置即可。

时间复杂度

1. 使用了按秩合并和路径压缩的并查集的操作时间复杂度可以近似看作常数
2. 生成并查集的时间是 $O(m)$
3. 生成连通子图的字符集合是 $O(n)$
4. 连通子图字符集排序最差的情况是都是一个集合中，$O(nlogn)$
5. 生成结果是 $O(n)$

$n = s 长度$
$m = pairs 长度$

所以时间复杂度大概是 $O(m+2n+nlogn)$

Swift 代码

class Solution {
    func smallestStringWithSwaps(_ s: String, _ pairs: [[Int]]) -> String {

        let sc = Array(s)
        let n = sc.count

        var uf: [Int] = (0..<n).map { $0 }
        var rk: [Int] = (0..<n).map { _ in 1 }

        func find(_ x: Int) -> Int {
            if uf[x] != x {
                uf[x] = find(uf[x])
            }
            return uf[x]
        }

        func union(_ x1: Int, _ x2: Int) {
            let fx1 = find(x1)
            let fx2 = find(x2)

            if fx1 != fx2 {
                if rk[fx1] < rk[fx2] {
                    uf[fx1] = fx2
                } else if rk[fx1] > rk[fx2] {
                    uf[fx2] = fx1
                } else {
                    uf[fx1] = fx2
                    rk[fx2] += 1
                }
            }
        }

        // 生成连通子图
        for p in pairs {
            let x1 = p[0]
            let x2 = p[1]

            union(x1, x2)
        }

        // 将同一个父节点的元素放到集合中
        var v: [Int: [Character]] = [:]
        for i in 0..<n {
            v[find(i), default: []].append(sc[i])
        }

        // 将同一连通子图内的字符集按倒序排序
        v = v.mapValues({ $0.sorted(by: >) })

        var res: [Character] = []

        for i in 0..<n {
            // 找到当前节点对应的连通子图，取出最后一个元素放到当前位置
            if let last = v[find(i)]?.popLast() {
                res.append(last)
            }
        }

        return String(res)
    }
}