1202. Smallest String With Swaps.md

1202. Smallest String With Swaps

---

leetcode-cn Daily Challenge on January 11th, 2021.

---

Difficulty : Medium

Related Topics : Array、UnionFind

---

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

• mine
  • Java
    • Runtime: 71 ms, faster than 37.41%, Memory Usage: 89.8 MB, less than 46.63% of Java online submissions

      public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
          int n = s.length();
          UF uf = new UF(n);
          for (List<Integer> p : pairs) {
              uf.unite(p.get(0), p.get(1));
          }
          char[] arr = s.toCharArray();
          //如果连通的  直接重排序
          if (uf.united()) {
              Arrays.sort(arr);
              return new String(arr);
          }
          //获取从前到后排列 并且已经排序的子集
          List<List<Integer>> parts = uf.getParts();
          for (List<Integer> p : parts) {
              char[] t = new char[p.size()];
              for (int i = 0; i < p.size(); i++) {
                  t[i] = arr[p.get(i)];
              }
              //对子集对应的值重新排序  并赋值到排序后的位置
              Arrays.sort(t);
              for (int i = 0; i < p.size(); i++) {
                  arr[p.get(i)] = t[i];
              }
          }
          return new String(arr);
      }
      
      class UF {
          int count;
          int[] arr;
          List<Integer>[] parts;
      
          public UF(int n) {
              count = n;
              arr = new int[n];
              parts = new List[n];
              for (int i = 0; i < n; i++) {
                  arr[i] = i;
                  parts[i] = new ArrayList<>(Arrays.asList(i));
              }
          }
      
          int find(int a) {
              if (a != arr[a]) {
                  arr[a] = find(arr[a]);
              }
              return arr[a];
          }
      
          boolean unite(int a, int b) {
              int ta = find(a);
              int tb = find(b);
              if (ta != tb) {
                  //将后面的子集添加到前面的子集中  保存当前子集在可交换的最前面
                  if (ta > tb) {
                      arr[ta] = tb;
                      parts[tb].addAll(parts[ta]);
                      parts[ta] = null;
                  } else {
                      arr[tb] = ta;
                      parts[ta].addAll(parts[tb]);
                      parts[tb] = null;
                  }
                  count--;
                  return true;
              }
              return false;
          }
      
          boolean united() {
              return count == 1;
          }
      
          List<List<Integer>> getParts() {
              List<List<Integer>> res = new ArrayList<>();
              for (List<Integer> p : parts) {
                  if (p == null) continue;
                  // 分组之后 给子集排好序，重新排列赋值时用
                  Collections.sort(p);
                  res.add(p);
              }
              return res;
          }
      }
      

---

• the most votes

• Runtime: 14 ms, faster than 99.45%, Memory Usage: 70.1 MB, less than 99.86% of Java online submissions

  public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
      int n = s.length();
      int[] parent = new int[n], count = new int[n];
      for (int i = 0; i < n; i++) {
          parent[i] = i;
          count[i] = 1;
      }
      for (List<Integer> p : pairs) {
          union(parent, count, p.get(0), p.get(1));
      }
      boolean[] visited = new boolean[n];
      char[] buf = new char[n];
      for (int i = 0, total = 0; i < n; i++) {
          int j = parent[i] = find(parent, i);
          if (!visited[j]) {
              visited[j] = true;
              int t = total + count[j];
              count[j] = total;
              total = t;
          }
          buf[count[j]++] = s.charAt(i);
      }
      int i0 = 0;
      for (int j : parent) {
          if (visited[j]) {
              visited[j] = false;
              int i1 = count[j];
              Arrays.sort(buf, i0, i1);
              i0 = i1;
          }
      }
      char[] result = new char[n];
      for (int i = n - 1; i >= 0; i--) {
          result[i] = buf[--count[parent[i]]];
      }
      return new String(result);
  }
  
  static void union(int[] parent, int[] count, int i, int j) {
      i = find(parent, i);
      j = find(parent, j);
      if (i == j) {
          return;
      }
      if (count[i] < count[j]) {
          parent[i] = j;
          count[j] += count[i];
      } else {
          parent[j] = i;
          count[i] += count[j];
      }
  }
  
  static int find(int[] parent, int i) {
      while (parent[i] != i) {
          int p = parent[i];
          parent[i] = parent[p];
          i = p;
      }
      return i;
  }
  

---