[B] [C] [D]

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]] output: "ABC" explanation: 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

Tip:

  • 1 <= s.length <= 10^5
  • 0 <= pairs.length <= 10^5
  • 0 <= pairs[i][0], pairs[i][1] < s.length
  • sContains only lowercase English letters

Their thinking

Because characters in an index pair relationship can be swapped arbitrarily, corresponding characters can be maintained into a collection based on an array of index pairs. Then sort the characters in the set and assemble the result string according to the sorted result. Because the process needs to merge sets frequently, and obtain the set of characters, so you can use and look up the set to solve the problem. If you do not understand and search set, you can see my article data structure – and search set, the paper introduces the concept of and search set, application scenarios and handwritten implementation of the whole process.

The demo

Code implementation

This. size = Array(n).fill(1); This. list = Array(n); for(let i = 0; i<n; i++){ this.list[i] = i; Find (x){if(this.list[x] === x) return x; Const root = this.find(this.list[x]) // Mount the current node as the root node, this.list[x] = root; return root; } const rootA = this.find(a),rootB = this.find(b); If (rootA === rootB) return; if(rootA == rootB) return; If (this.size[rootA]>this.size[rootB]){this.list[rootB] = rootA; // If (this.size[rootA]>this.size[rootB]){this.list[rootB] = rootA; Size [rootA] += this.size[rootB]}else{// If (rootA = rootB) {this.list[rootA] = rootB; this.size[rootB] += this.size[rootA] } } } var smallestStringWithSwaps = function(s, Const len =s.length, // new unionset = new unionset (len); For (let I = 0; i<pairs.length; I ++){merge(pairs[I][0],pairs[I][1])} // Merge (pairs[I][0],pairs[I][1]) const map = new map (); for(let i = 0; i<len; i++){ const root = unionset.find(i); if(map.has(root)){ const item = map.get(root); Item.vals. Push (S [I]) item.inds. Push (I)}else{map.set(root,{vals:[S [I]],inds:[I]})}} const arr = Array(len); ForEach (item => {// Sort item.vals. Sort () for characters and subscripts in each set; item.inds.sort((a,b) => a-b); For (let I = 0; i<item.vals.length; I++) {arr [item inds [I]] = item. The vals [I]}}) / / returns the value of the return arr. Join (' ')};Copy the code

At this point we are done with Leetcode-1202 – exchanging elements in the string

If you have any questions or suggestions, please leave a comment!