Problem 25.5 · Union-Find (DSU)Medium

Smallest String With Swaps

What it teaches: Swaps are transitive: within a connected group of indices, any arrangement is reachable, so sort each group.

Practise it on judges as “Smallest String With Swaps”.

The problem

You may swap the characters at index pairs pairs[i] any number of times. Return the lexicographically smallest string you can make.

Example 1

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

Constraints

1 ≤ s.length ≤ 10⁵

Pattern clues in the wording

→ Repeated swaps = free rearrangement within a group

These clues point to Union-Find: Keep each group as a tree with a root; find the root to test membership and link roots to merge groups.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        return s;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	s = "dcab" pairs = [[0,3],[1,2]]	"bacd"
2	s = "dcab" pairs = [[0,3],[1,2],[0,2]]	"abcd"
3	s = "cba" pairs = [[0,1],[1,2]]	"abc"

From slow to fast

Approaches

1. Group indices, sort letters per group · O((n + p) α(n) + 26n)

Group indices, sort letters per group

Time O((n + p) α(n) + 26n) Space O(26n) worst case

Union the pairs. For each root, keep a count of its letters (26 buckets). Walk indices left to right and give each the smallest remaining letter from its root's bucket.

Approach 1

import java.util.*;

class Solution {
    private 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) parent[find(p.get(0))] = find(p.get(1));
        Map<Integer, int[]> counts = new HashMap<>();
        for (int i = 0; i < n; i++) counts.computeIfAbsent(find(i), k -> new int[26])[s.charAt(i) - 'a']++;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int[] c = counts.get(find(i));
            int k = 0;
            while (c[k] == 0) k++;
            c[k]--;
            sb.append((char) ('a' + k));
        }
        return sb.toString();
    }

    private int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

Verdict: Counting avoids sorting each group.

Before you submit

Edge cases and common mistakes

Test these inputs

No pairs (unchanged)
All indices connected (fully sorted)

Mistakes people make

Applying swaps greedily one at a time.

Interview

Follow-up questions

Why is any permutation within a group reachable?

Command Palette

The problem

Approaches

Group indices, sort letters per group

Edge cases and common mistakes

Follow-up questions