Smallest String With Swaps

Medium Graphs Connected Components Original on LeetCode

Smallest String With Swaps is a medium graphs problem solved with the connected components pattern. The best approach, optimal (union-find, then sort each group), runs in O((n + p) · α(n) + n log n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (label propagation, then sort each group) up.

Problem

You are given a string s and a list pairs, where each pairs[i] = [a, b] names two positions of s (0-indexed) whose characters may be swapped.

Each listed swap can be performed as many times as you like and in any order. Return the lexicographically smallest string you can turn s into.

Examples

Example 1

Input
s = "dcab", pairs = [[0, 3], [1, 2]]
Output
"bacd"
Why
Positions 0 and 3 can trade, giving "bcad"; positions 1 and 2 can trade, giving "bacd".

Example 2

Input
s = "zxyw", pairs = [[0, 1], [1, 2], [2, 3]]
Output
"wxyz"
Why
The pairs chain all four positions together, so the letters can be rearranged freely and sorted.

Example 3

Input
s = "mango", pairs = []
Output
"mango"
Why
With no pairs nothing can move.

Constraints

  • 1 <= s.length <= 10^5
  • 0 <= pairs.length <= 10^5
  • 0 <= pairs[i][0], pairs[i][1] < s.length
  • s contains only lowercase English letters.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (label propagation, then sort each group)O(n · (n + p) + n log n)O(n)
Optimal (union-find, then sort each group)O((n + p) · α(n) + n log n)O(n)

1Brute force (label propagation, then sort each group)

TimeO(n · (n + p) + n log n)The smallest label can need up to n sweeps to travel along a long chain, and each sweep scans all p pairs; sorting the groups adds n log n.
SpaceO(n)Labels, the buckets and the output array.

Give every index a label equal to itself. Sweep over all pairs again and again, setting both ends of each pair to the smaller of their two labels, until a full sweep changes nothing. At that point every connected group shares one label. Then gather each group's positions (already in increasing order) and letters, sort the letters, and write them back.

  1. label[i] = i for every index.
  2. Repeat: for each pair (a, b), set both labels to min(label[a], label[b]); stop when nothing changed in a sweep.
  3. Bucket the indices by label, in increasing index order.
  4. For each bucket, sort its letters and place them into its indices left to right.
class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        int[] label = new int[n];
        for (int i = 0; i < n; i++) label[i] = i;
        boolean changed = true;
        while (changed) {
            changed = false;
            for (List<Integer> p : pairs) {
                int a = p.get(0), b = p.get(1);
                int m = Math.min(label[a], label[b]);
                if (label[a] != m || label[b] != m) {
                    label[a] = m;
                    label[b] = m;
                    changed = true;
                }
            }
        }
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) groups.computeIfAbsent(label[i], x -> new ArrayList<>()).add(i);
        char[] out = new char[n];
        for (List<Integer> idx : groups.values()) {
            char[] letters = new char[idx.size()];
            for (int j = 0; j < idx.size(); j++) letters[j] = s.charAt(idx.get(j));
            Arrays.sort(letters);
            for (int j = 0; j < idx.size(); j++) out[idx.get(j)] = letters[j];
        }
        return new String(out);
    }
}

2Optimal (union-find, then sort each group)

TimeO((n + p) · α(n) + n log n)Each union/find is almost constant (inverse Ackermann); sorting all groups together costs at most n log n.
SpaceO(n)Parent and size arrays, the groups and the output.

Use a disjoint-set union to merge the two ends of every pair in near-constant time. Each root then identifies one connected group of positions. Because any permutation is possible inside a group, the best result puts the group's letters in sorted order into its positions from left to right.

  1. parent[i] = i; for each pair, union its two ends (path halving in find, union by size).
  2. Walk i from 0 to n - 1 and append i to the list of find(i).
  3. For each list, sort the letters at those positions and write them back in order.
class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        int[] parent = new int[n], size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        for (List<Integer> p : pairs) {
            int a = find(parent, p.get(0)), b = find(parent, p.get(1));
            if (a == b) continue;
            if (size[a] < size[b]) { int t = a; a = b; b = t; }
            parent[b] = a;
            size[a] += size[b];
        }
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) groups.computeIfAbsent(find(parent, i), x -> new ArrayList<>()).add(i);
        char[] out = new char[n];
        for (List<Integer> idx : groups.values()) {
            char[] letters = new char[idx.size()];
            for (int j = 0; j < idx.size(); j++) letters[j] = s.charAt(idx.get(j));
            Arrays.sort(letters);
            for (int j = 0; j < idx.size(); j++) out[idx.get(j)] = letters[j];
        }
        return new String(out);
    }

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

Edge cases to test

  • No pairs at all: the string is returned unchanged
  • A pair that connects an index with itself
  • The same pair listed several times, or in both orders
  • Pairs that link positions only indirectly, like (0, 4) and (4, 2)
  • A single character

Hints

Hint 1

A swap can be used any number of times. If position a can swap with b and b with c, can the letter at a end up at c?

Hint 2

Treat indices as nodes and pairs as edges. Inside one connected group, any arrangement of the group's letters is reachable.

Hint 3

Find the groups (union-find is a good fit), then sort each group's letters and write them back into the group's positions from left to right.

FAQ

What is the best time complexity for Smallest String With Swaps?

Optimal (union-find, then sort each group) runs in O((n + p) · α(n) + n log n) time and O(n) extra space. Each union/find is almost constant (inverse Ackermann); sorting all groups together costs at most n log n.

Which pattern does Smallest String With Swaps use?

It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces, Number of Islands, Evaluate Division.

Is there a brute force solution for Smallest String With Swaps?

Yes. Brute force (label propagation, then sort each group) takes O(n · (n + p) + n log n) time and O(n) space. Give every index a label equal to itself.

Which edge cases should I test for Smallest String With Swaps?

No pairs at all: the string is returned unchanged; A pair that connects an index with itself; The same pair listed several times, or in both orders; Pairs that link positions only indirectly, like (0, 4) and (4, 2); A single character.