Smallest String With Swaps — Medium Problem & Solution

You are given a string s and a list pairs of index pairs. You may swap the characters at any listed pair any number of times, in any order.

Difficulty: Medium
Topics: Strings, Hash Table, Sorting, Union Find
Asked at: Amazon, Google, Uber
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string s and a list pairs of index pairs. You may swap the characters at any listed pair any number of times, in any order.

Return the lexicographically smallest string reachable this way.

Example 1

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: bacd
Explanation: Indices 0 and 3 can swap, as can 1 and 2, giving two independent pairs.

Example 2

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: abcd
Explanation: The third pair links everything into one group, so all four characters can be sorted freely.

Example 3

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: abc

Constraints

1 <= s.length <= 100000
0 <= pairs.length <= 100000
0 <= pairs[i][0], pairs[i][1] < s.length
s consists of lowercase English letters.

How to solve Smallest String With Swaps

Swapping along edges any number of times generates every permutation within a connected component. So the smallest string sorts each component's multiset of characters into its component's sorted index list.

Approach

Union the indices of every pair with a disjoint-set structure.
Group the indices by their component root.
For each group, collect its characters, sort them, and write them back into the group's indices in increasing index order.

Why it works

Transpositions along a connected graph generate the full symmetric group on its vertices, so any arrangement of a component's characters is reachable. Placing the smallest available character at the smallest index of the component is greedily optimal and cannot be beaten, because positions in different components are independent.

Complexity

Time — O(n log n + p α(n))
Space — O(n)

Pitfalls

Swapping only the listed pairs once misses arrangements that need a chain of swaps.
Sorting the whole string ignores the component boundaries and is wrong whenever the graph is disconnected.
Path compression matters: without it the union-find degrades badly at the stated limits.

Reference solution

Python

from typing import List

def smallestStringWithSwaps(s: str, pairs: List[List[int]]) -> str:
    n = len(s)
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for a, b in pairs:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
    groups = {}
    for i in range(n):
        groups.setdefault(find(i), []).append(i)
    out = list(s)
    for idx in groups.values():
        chars = sorted(s[i] for i in idx)
        for t, i in enumerate(idx):
            out[i] = chars[t]
    return "".join(out)

JavaScript

var smallestStringWithSwaps = function(s, pairs) {
    var n = s.length;
    var parent = [];
    for (var t = 0; t < n; t++) parent.push(t);
    var find = function(x) {
        while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    };
    for (var p = 0; p < pairs.length; p++) {
        var a = find(pairs[p][0]), b = find(pairs[p][1]);
        if (a !== b) parent[a] = b;
    }
    var groups = {};
    for (var i = 0; i < n; i++) {
        var r = String(find(i));
        if (groups[r] === undefined) groups[r] = [];
        groups[r].push(i);
    }
    var out = s.split("");
    var keys = Object.keys(groups);
    for (var k = 0; k < keys.length; k++) {
        var idx = groups[keys[k]];
        var chars = [];
        for (var m = 0; m < idx.length; m++) chars.push(s.charAt(idx[m]));
        chars.sort();
        for (var q = 0; q < idx.length; q++) out[idx[q]] = chars[q];
    }
    return out.join("");
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue