Course4all

Smallest String With Swaps

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Union Find.

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

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMost Stones Removed
Next Question →Bricks Falling When Hit