题目

1202. 交换字符串中的元素

给你一个字符串 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"

解法一

思路

并查集。

一个连通分量里的字符可以任意次的更换位置，该题的要点就是，将各个连通分量的字符排序。

我们可以按pairs关系数组，将字符合并成对应的连通分量，然后将字符在各自的连通分量里排序，再遍历字符串，每次循环，看当前下标在哪个连通分量里，去该连通分量里找最小的即可。

1. 遍历pairs关系数组，将字符对应的下表按关系数组合并。
2. 遍历字符串，将字符按连通量分组，存入map对象，key为该连通分量顶级元素的下标，value为字符数组
3. 遍历map对象，将各连通分量里的字符按charCode将序排列
4. 新建一个结果数组，遍历字符串，每次从当前下表所在的连通分量里pop弹出一个字符再push到数组里，由于刚才是将序排列的，这里操作完之后，各连通分量对应的字符在结果数组里是升序排列的
5. 将结果数组合并成字符串返回。

代码如下

/** * @param {string} s * @param {number[][]} pairs * @return {string} */
function smallestStringWithSwaps(s, pairs) {
    if (pairs.length === 0) return s;

    let uf= new UnionFind(s.length);
    // 将字符的下标按pairs关系数组合并
    for (let [x, y] of pairs) {
        uf.union(x, y);
    }

    let map = {};
    // 将字符按连通量关系，存入map中，key为连通分量顶级元素的下标，value为该连通分量所有的字符
    for (let i = 0; i < s.length; i++) {
        let root = uf.find(i);
        if (!(root in map)){
            map[root] = [];
        }
        map[root].push(s[i]);
    }
    // 将每个连通分量里的字符按charCode降序排序，即dcba这样
    for (let k in map) {
        map[k].sort(
            (a, b) => b.charCodeAt(0) - a.charCodeAt(0),
        );
    }

    let res = new Array(s.length);
    // 遍历字符串，找当前下标所在的连通分量，弹出最后一个填入数组中，由于刚才是降序排列，这里在单个连通分量中是升序的
    for (let i = 0; i < s.length; i++) {
        let root = uf.find(i);
        let strings = map[root];
        res[i] = strings.pop();
    }

    // 将字符串数组合并成字符串返回
    return res.join('');
}

class UnionFind {

    constructor(size) {
        this.parent = Array(size)
            .fill(0)
            .map((el, i) => i);
        this.rank = Array(size).fill(0);
        this.count = size;
    }

    size() {
        return this.count;
    }

    find(x) {
        if (this.parent[x] !== x) {
            // 路径压缩
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(p, q) {
        let rootP = this.find(p);
        let rootQ = this.find(q);
        if (rootP === rootQ) return;
        // 按秩合并
        if (this.rank[rootP] > this.rank[rootQ]) {
            this.parent[rootQ] = rootP;
        } else {
            this.parent[rootP] = rootQ;
            this.rank[rootP] === this.rank[rootQ] && ++this.rank[rootQ];
        }
        this.count--;
    }
}