Course4all
Join us on telegram
Home/dsa/Union Find/Smallest String With Swaps

Smallest String With Swaps

Master this topic with zero to advance depth.

Smallest String With Swaps

Given a string s and pairs of indices that can be swapped, return the lexicographically smallest string possible.

Medium

Examples

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Approach 1

Level III: Union-Find + Sorting (Optimal)

Intuition

Indices that can swap form connected components. All characters within a component can be moved to any index in that component. Sort characters for each component and place them in sorted index order.

⏱ O(N \log N)💾 O(N)

Detailed Dry Run

Indices {0, 3} are connected. Characters are s[0]='d', s[3]='b'. Sorted: 'b', 'd'. Place 'b' at index 0 and 'd' at index 3.

java
import java.util.*;
class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length(); int[] p = new int[n]; for(int i=0; i<n; i++) p[i]=i;
        for(List<Integer> pair : pairs) union(p, pair.get(0), pair.get(1));
        Map<Integer, PriorityQueue<Character>> groups = new HashMap<>();
        for(int i=0; i<n; i++) {
            int root = find(p, i);
            groups.computeIfAbsent(root, k -> new PriorityQueue<>()).offer(s.charAt(i));
        }
        StringBuilder res = new StringBuilder();
        for(int i=0; i<n; i++) res.append(groups.get(find(p, i)).poll());
        return res.toString();
    }
    private int find(int[] p, int i) { return p[i]==i?i:(p[i]=find(p, p[i])); }
    private void union(int[] p, int i, int j) { int r1=find(p,i), r2=find(p,j); if(r1!=r2) p[r1]=r2; }
}
← Previous QuestionMost Stones Removed
Next Question →Bricks Falling When Hit