# 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.

``````class Solution {
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.size();
vector<vector<int>> g(n);
vector<bool> visited(n);
for (auto &pair : pairs) {
g[pair[0]].push_back(pair[1]);
g[pair[1]].push_back(pair[0]);
}
for (int i = 0; i < n; ++i) {
if (visited[i]) continue;
vector<int> pos;
helper(g, i, pos, visited);
string t;
for (int idx : pos) t += s[idx];
sort(pos.begin(), pos.end());
sort(t.begin(), t.end());
for (int j = 0; j < pos.size(); ++j) {
s[pos[j]] = t[j];
}
}
return s;
}
void helper(vector<vector<int>>& g, int i, vector<int>& pos, vector<bool>& visited) {
visited[i] = true;
pos.push_back(i);
for (int next : g[i]) {
if (visited[next]) continue;
helper(g, next, pos, visited);
}
}
};
``````

``````class Solution {
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.size();
vector<int> root(n, -1);
vector<vector<int>> g(n);
for (auto &pair : pairs) {
int x = find(root, pair[0]), y = find(root, pair[1]);
if (x != y) {
root[x] = y;
}
}
for (int i = 0; i < n; ++i) {
g[find(root, i)].push_back(i);
}
for (auto &a : g) {
string t;
for (int idx : a) t += s[idx];
sort(t.begin(), t.end());
for (int i = 0; i < a.size(); ++i) {
s[a[i]] = t[i];
}
}
return s;
}
int find(vector<int>& root, int i) {
return root[i] < 0 ? i : root[i] = find(root, root[i]);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1202

Minimize Hamming Distance After Swap Operations

https://leetcode.com/problems/smallest-string-with-swaps/

https://leetcode.com/problems/smallest-string-with-swaps/discuss/388257/C%2B%2B-with-picture-union-find

https://leetcode.com/problems/smallest-string-with-swaps/discuss/800257/C%2B%2B-DFS-solution-or-O(n-logn)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation