Formatted question description: https://leetcode.ca/all/1202.html

1202. Smallest String With Swaps (Medium)

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.

Related Topics:
Array, Union Find

Solution 1. Union Find

// OJ: https://leetcode.com/problems/smallest-string-with-swaps/
// Time: O(NlogN)
// Space: O(N)
class Solution {
    vector<int> id;
    int find(int x) {
        return id[x] == x ? x : (id[x] = find(id[x]));
    }
    void connect(int x, int y) {
        int p = find(x), q = find(y);
        id[p] = q;
    }
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& A) {
        int N = s.size();
        id.assign(N, 0);
        iota(begin(id), end(id), 0);
        for (auto &p : A) connect(p[0], p[1]);
        unordered_map<int, vector<int>> m;
        for (int i = 0; i < N; ++i) m[find(i)].push_back(i);
        for (auto &[k, v] : m) sort(begin(v), end(v), [&](int a, int b) { return s[a] > s[b]; });
        string ans;
        for (int i = 0; i < N; ++i) {
            ans += s[m[find(i)].back()];
            m[find(i)].pop_back();
        }
        return ans;
    }
};

Java

  • class Solution {
        public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
            Map<Integer, Set<Integer>> adjacentMap = new HashMap<Integer, Set<Integer>>();
            for (List<Integer> pair : pairs) {
                int index1 = pair.get(0), index2 = pair.get(1);
                Set<Integer> set1 = adjacentMap.getOrDefault(index1, new HashSet<Integer>());
                Set<Integer> set2 = adjacentMap.getOrDefault(index2, new HashSet<Integer>());
                set1.add(index2);
                set2.add(index1);
                adjacentMap.put(index1, set1);
                adjacentMap.put(index2, set2);
            }
            char[] array = s.toCharArray();
            int length = array.length;
            int[] groups = new int[length];
            Arrays.fill(groups, -1);
            Map<Integer, Set<Integer>> groupNumsMap = new HashMap<Integer, Set<Integer>>();
            int groupNum = 0;
            int ungrouped = length;
            Queue<Integer> queue = new LinkedList<Integer>();
            int startIndex = 0;
            while (ungrouped > 0) {
                while (startIndex < length && groups[startIndex] >= 0)
                    startIndex++;
                if (startIndex < length)
                    queue.offer(startIndex);
                Set<Integer> groupSet = new HashSet<Integer>();
                while (!queue.isEmpty()) {
                    int index = queue.poll();
                    if (groups[index] < 0) {
                        groups[index] = groupNum;
                        groupSet.add(index);
                        ungrouped--;
                        Set<Integer> adjacentSet = adjacentMap.getOrDefault(index, new HashSet<Integer>());
                        for (int adjacent : adjacentSet) {
                            if (groups[adjacent] < 0)
                                queue.offer(adjacent);
                        }
                    }
                }
                groupNumsMap.put(groupNum, groupSet);
                groupNum++;
                startIndex++;
            }
            boolean[] sorted = new boolean[length];
            for (int i = 0; i < length; i++) {
                if (!sorted[i]) {
                    int group = groups[i];
                    if (group >= 0) {
                        List<Integer> indicesList = new ArrayList<Integer>(groupNumsMap.get(group));
                        Collections.sort(indicesList);
                        StringBuffer sb = new StringBuffer();
                        for (int index : indicesList)
                            sb.append(array[index]);
                        char[] subsequence = sb.toString().toCharArray();
                        Arrays.sort(subsequence);
                        int size = indicesList.size();
                        for (int j = 0; j < size; j++) {
                            int index = indicesList.get(j);
                            array[index] = subsequence[j];
                            sorted[index] = true;
                        }
                    }
                }
            }
            return new String(array);
        }
    }
    
  • // OJ: https://leetcode.com/problems/smallest-string-with-swaps/
    // Time: O(NlogN)
    // Space: O(N)
    class Solution {
        vector<int> id;
        int find(int x) {
            return id[x] == x ? x : (id[x] = find(id[x]));
        }
        void connect(int x, int y) {
            int p = find(x), q = find(y);
            id[p] = q;
        }
    public:
        string smallestStringWithSwaps(string s, vector<vector<int>>& A) {
            int N = s.size();
            id.assign(N, 0);
            iota(begin(id), end(id), 0);
            for (auto &p : A) connect(p[0], p[1]);
            unordered_map<int, vector<int>> m;
            for (int i = 0; i < N; ++i) m[find(i)].push_back(i);
            for (auto &[k, v] : m) sort(begin(v), end(v), [&](int a, int b) { return s[a] > s[b]; });
            string ans;
            for (int i = 0; i < N; ++i) {
                ans += s[m[find(i)].back()];
                m[find(i)].pop_back();
            }
            return ans;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions