The title

1202. Exchange elements in a string

You are given a string s and an array of “index pairs” in that string, pairs[I] = [a, b] representing two indexes (numbered from 0) in the string.

You can swap characters at any pair of indexes in pairs as many times as you want.

Returns the smallest lexicographical string that s can become after a number of swaps.

Example 1:

Input: s = "dcab", pairs = [[0, 3], [1, 2]] output: "bacd" explanation: exchange s [0] and [3] s, s = "bcad exchange" s [1] and [2] s, s = "bacd"Copy the code

Example 2:

Input: s = "dcab", pairs = [[0, 3], [1, 2], [0, 2]] output: "abcd" explanation: Swap s[0] and S [3], s = "bcad" swap S [0] and S [2], s = "ACbd" swap S [1] and S [2], s = "ABCD"Copy the code

Example 3:

Input: s = "cba", pairs = [0,1],[1,2]] Exchange s [0] and [1] s, s = "bca exchange" s [1] and [2] s, s = "bac" exchange s [0] and [1] s, s = "ABC"Copy the code

Method a

Train of thought

Check and set.

Characters in a connected component can be changed any number of times, and the main point of the problem is to sort the characters of each connected component.

We can combine the characters into the corresponding connected components according to the pairs relational array, and then sort the characters in their connected components. We iterate through the string again, each time, to see which connected component the current subscript is in, and find the smallest one in the connected component.

1. Iterate through the Pairs relational array and merge the following table corresponding to the characters as a relational array.
2. Iterate over the string, group the characters according to the connected flux, and store them in the Map object. Key is the subscript of the top element of the connected component, and value is the character array
3. Traverses the map and arranges the characters in the connected components in charCode order
4. Create a new result array, iterate through the string, each time pop a character from the connected component of the current table and push it into the array, because the order was just done, after this operation, the connected components corresponding to the characters in the result array will be in ascending order
5. Returns the result array as a string.

The following code

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

    let uf= new UnionFind(s.length);
    // Combine the subscripts of characters as pairs relational arrays
    for (let [x, y] of pairs) {
        uf.union(x, y);
    }

    let map = {};
    Key is the subscript of the top element of the connected component, and value is all the characters of the connected component
    for (let i = 0; i < s.length; i++) {
        let root = uf.find(i);
        if(! (rootin map)){
            map[root] = [];
        }
        map[root].push(s[i]);
    }
    // Order the characters in each connected component in descending charCode order, i.e. Dcba
    for (let k in map) {
        map[k].sort(
            (a, b) = > b.charCodeAt(0) - a.charCodeAt(0)); }let res = new Array(s.length);
    // Traverses the string to find the connected component of the current index, and pops the last one into the array
    for (let i = 0; i < s.length; i++) {
        let root = uf.find(i);
        let strings = map[root];
        res[i] = strings.pop();
    }

    // Merge an array of strings into a string
    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) {// Path compression
            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;
        // rank merge
        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--; }}Copy the code