Welcome to Subscribe On Youtube
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^50 <= pairs.length <= 10^50 <= pairs[i][0], pairs[i][1] < s.lengthsonly 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;
}
};
-
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); } } ############ class Solution { private int[] p; public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) { int n = s.length(); p = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; } for (List<Integer> pair : pairs) { p[find(pair.get(0))] = find(pair.get(1)); } Map<Integer, PriorityQueue<Character>> mp = new HashMap<>(); char[] chars = s.toCharArray(); for (int i = 0; i < n; ++i) { mp.computeIfAbsent(find(i), k -> new PriorityQueue<>()).offer(chars[i]); } for (int i = 0; i < n; ++i) { chars[i] = mp.get(find(i)).poll(); } return new String(chars); } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } } -
// 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; } }; -
class Solution: def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] n = len(s) p = list(range(n)) for a, b in pairs: p[find(a)] = find(b) mp = defaultdict(list) for i, c in enumerate(s): heappush(mp[find(i)], c) return ''.join(heappop(mp[find(i)]) for i in range(n)) -
func smallestStringWithSwaps(s string, pairs [][]int) string { n := len(s) p := make([]int, n) for i := range p { p[i] = i } var find func(x int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } for _, pair := range pairs { p[find(pair[0])] = find(pair[1]) } mp := make(map[int][]rune) for i, c := range s { mp[find(i)] = append(mp[find(i)], c) } for _, v := range mp { sort.Slice(v, func(i, j int) bool { return v[i] < v[j] }) } var ans []rune for i := 0; i < n; i++ { ans = append(ans, mp[find(i)][0]) mp[find(i)] = mp[find(i)][1:] } return string(ans) }