1202

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.

Companies: Google, Amazon, Microsoft

Related Topics:
Hash Table, String, Depth-First Search, Breadth-First Search, Union Find

Similar Questions:

• Minimize Hamming Distance After Swap Operations (Medium)
• Process Restricted Friend Requests (Medium)
• Largest Number After Digit Swaps by Parity (Medium)
• Lexicographically Smallest Beautiful String (Medium)

Solution 1. Union Find

// OJ: https://leetcode.com/problems/smallest-string-with-swaps/
// Author: github.com/lzl124631x
// Time: O((N + P) * logN)
// Space: O(N)
class UnionFind {
    vector<int> id;
public:
    UnionFind(int n) : id(n) {
        iota(begin(id), end(id), 0);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        id[find(a)] = find(b);
    }
};
class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& P) {
        int N = s.size();
        UnionFind uf(N);
        for (auto &p : P) uf.connect(p[0], p[1]);
        unordered_map<int, vector<int>> m; // root index -> set of indices in the same group
        for (int i = 0; i < N; ++i) m[uf.find(i)].push_back(i);
        for (auto &[r, v] : m) sort(begin(v), end(v), [&](int a, int b) { return s[a] > s[b]; });
        string ans(N, 0);
        for (int i = 0; i < N; ++i) {
            ans[i] = s[m[uf.find(i)].back()];
            m[uf.find(i)].pop_back();
        }
        return ans;
    }
};