Skip to content

1202. Smallest String With Swaps

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:

Intuition:

Remember, our first task is to determine which indices belong to the same connected component. In this approach, we will use the Union-Find data structure to accomplish this.

First, we will union all vertices that share an edge (vertices a and b share an edge if (a, b) or (b, a) exists in pairs ). After which, all vertices with the same root will belong to the same component. This way, by looking at the root node for each vertex, we can put the vertices and the characters at these vertices (indices) in separate lists corresponding to the component they belong to. Then, similar to the previous approach, we will sort the list of characters that belong to the same component and place the \(i_{th}\) character at the \(i_{th}\) index in a string smallestString.

Note that we don't need to sort the list of indices in this approach because, as we iterate over vertices in ascending order, we will store the vertices that belong to the same component in ascending order.

Algorithm:

  1. Iterate over the pairs, for each pair (a, b) perform the union operation for vertices a and b.

  2. Iterate over the indices from 0 to s.size() - 1. For each index (vertex) we will:

  • Perform the find operation on vertex to find the root.
  • Store the vertex in the list corresponding to root in the HashMap rootToComponent.
  1. Iterate over each list in the HashMap rootToComponent:
  • For each list indices, iterate over the list and for each element store the corresponding character in s in the list of characters (characters). Here, each element in indices represents an index in s and each character in characters represents the characters at this index in s
  • Sort the list and characters.
  • Iterate over the lists indices and characters, place the ith character at the ith index in the string smallestString.
  1. Return smallestString.

Disjoint Set Union (DSU)

看不懂题再次呈现

“Return the lexicographically smallest string that s can be changed to after using the swaps.”

返回最小的字母排序顺序

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        UnionFind uf = new UnionFind(n);

        for (List<Integer> pair : pairs){
            uf.union(pair.get(0), pair.get(1));
        }
                // uf
        // root: 0, 1, 2, 3
        //       0  1  1  0
        //       
        Map<Integer, List<Character>> componentMap = new HashMap<>();
        for (int i = 0; i < n; i++){
            int root = uf.find(i);
            componentMap.putIfAbsent(root, new ArrayList<>());
            componentMap.get(root).add(s.charAt(i));
        }
      // 创建 componentMap，键为组件的根节点，值为该组件包含的字符列表
                    // 0: d,b
        // 1: c,a
        for (List<Character> component : componentMap.values()){
            Collections.sort(component);
        }
      // 对每个组件内的字符列表进行排序，使得在构建最终字符串时，可以按字典序优先使用最小的字符。

         StringBuilder sb = new StringBuilder(s);
        // dcab
      // 把s copy 到sb里 变成可变的
        Map<Integer, Integer> indexMap = new HashMap<>();
        // 0, 1
        // 1, 2
        for (int i = 0; i < n; i++){
            int root = uf.find(i);  // 2, 3
            // 0 , 1  // 2-> 1 // 0
            int index = indexMap.getOrDefault(root, 0);
            // 0,  1, 0 // 1 // root 
            sb.setCharAt(i, componentMap.get(root).get(index));
            // dcab    0: b, d      0
            // bcab    1: a,c
            // baab    1: a,c
            // bacd
            indexMap.put(root, index + 1);
            // 
        }

        return sb.toString();
    }
}

class UnionFind{
    int[] root;
    int[] rank;
    public UnionFind(int n){
        root = new int[n];
        rank = new int[n];

        for (int i = 0; i < n; i++){
            root[i] = i;
            rank[i] = 1;
        }


    }

    public int find(int x){
        while(x != root[x]){
            x = root[x];
        }

        return x;
    }

    public void union(int x, int y){
        int rootX = find(x);
        int rootY = find(y);

        if (rank[rootX] < rank[rootY]){
            root[rootX] = rootY; 
        }else if (rank[rootX] > rank[rootY]){
            root[rootY] = rootX;

        }else{
            root[rootY] = rootX;
            rank[rootX]++;
        }
    }

    public boolean isC(int x, int y){
        return find(x) == find(y);
    }
}

// TC: O(nlogn)
// SC: O(n)