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);
}
}