Smallest String With Swaps

Description

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.

 

Example 1:

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"

Example 2:

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"

Example 3:

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"

 

Constraints:

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

Solution(javascript)

class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((val, index) => index)
    this.size = new Array(n).fill(1)
    this.count = n
  }

  root(i) {
    while (this.parent[i] !== undefined && i !== this.parent[i]) {
      this.parent[i] = this.parent[this.parent[i]] // Path compression
      i = this.parent[i]
    }
    return i
  }

  connected(a, b) {
    return this.root(a) === this.root(b)
  }

  union(a, b) {
    const rootA = this.root(a)
    const rootB = this.root(b)
    if (rootA === rootB) {
      return
    }
    if (this.parent[rootA] < this.parent[rootB]) {
      this.parent[rootA] = rootB
      this.size[rootB] += this.size[rootA]
    } else {
      this.parent[rootB] = rootA
      this.size[rootA] += this.size[rootB]
    }
    this.count -= 1
  }

  getCount() {
    return this.count
  }
}
/**
 * @param {string} s
 * @param {number[][]} pairs
 * @return {string}
 */
const smallestStringWithSwaps = function (s, pairs) {
  const result = []
  const uf = new UnionFind(s.length)
  pairs.forEach(([index1, index2]) => {
    uf.union(index1, index2)
  })
  const groups = {

  }

  for (let i = 0; i < s.length; i++) {
    const currentRoot = uf.root(i)
    if (groups[currentRoot]) {
      groups[currentRoot].add(i)
    } else {
      groups[currentRoot] = new Set([i])
    }
  }
  // leetcode 的JS环境是 10.15.0
  Object.values(groups).forEach((indexSet) => {
    const indexes = [...indexSet]
    const str = indexes.map(index => s[index])
    // NOTE node 12.12.0  竟然可以这样写 str.sort(([a, b]) => a.localeCompare(b))
    str.sort((a, b) => a.localeCompare(b))
    str.forEach((item, index) => {
      const realIndex = indexes[index]
      result[realIndex] = item
    })
  })
  return result.join('')
}