Given a string s and pairs of indices, you can swap any pair any number of times. Return the lexicographically smallest string possible.
Input: s="dcab", pairs=[[0,3],[1,2]] → Output: "bacd"Input: s="dcab", pairs=[[0,3],[1,2],[0,2]] → Output: "abcd"
Union-Find: connected components of indices can be freely permuted. Sort each component and place characters in sorted order.
- Union-Find on indices 0..n-1.
- Group indices by their root (use Map>).
- For each group: sort the characters, sort the indices.
- Assign sorted chars to sorted indices.
import java.util.*;
class Solution {
int[] parent;
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int n = s.length();
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (List<Integer> p : pairs) union(p.get(0), p.get(1));
Map<Integer, List<Integer>> groups = new HashMap<>();
for (int i = 0; i < n; i++) groups.computeIfAbsent(find(i), k->new ArrayList<>()).add(i);
char[] res = new char[n];
for (List<Integer> indices : groups.values()) {
List<Character> chars = new ArrayList<>();
for (int i : indices) chars.add(s.charAt(i));
Collections.sort(indices); Collections.sort(chars);
for (int i = 0; i < indices.size(); i++) res[indices.get(i)] = chars.get(i);
}
return new String(res);
}
private int find(int x) { return parent[x]==x?x:(parent[x]=find(parent[x])); }
private void union(int a, int b) { parent[find(a)] = find(b); }
}
- Time Complexity: O(N log N + E * alpha(N))
- Space Complexity: O(N)