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^50 <= pairs.length <= 10^50 <= pairs[i][0], pairs[i][1] < s.lengthsonly contains lower case English letters.
Sol:
Union find. And sort the chars inside each group. (using pq)
class Solution {
public:
int find_root(int x, vector<int>& par){
if(par[x] == x) return x;
else return par[x] = find_root(par[x], par);
}
void union_two(int x, int y, vector<int>& par, vector<int>& cnt){
int xx = find_root(x, par);
int yy = find_root(y, par);
if(cnt[xx] > cnt[yy]) swap(xx,yy);
if(cnt[xx] == cnt[yy])cnt[yy]++;
par[xx] = yy;
}
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
map<int, priority_queue<char, vector<char>, greater<char>> > pq;
int n = s.size();
vector<int> par(n);
vector<int> cnt(n);
for(int i = 0; i< n;i++){
par[i] = i;
cnt[i] = 1;
}
for(int i = 0; i<pairs.size(); i++){
union_two(pairs[i][0],pairs[i][1], par, cnt);
}
for(int i = 0; i<n; i++){
pq[find_root(i, par)].push(s[i]);
}
string ans;
for(int i =0; i<n; i++){
int r= par[i];
ans += pq[r].top();
pq[r].pop();
}
return ans;
}
};