Smallest String With Swaps

Smallest String With Swaps medium

Description

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices (0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

Examples

> Case 1:
    s = "dcab", pairs = [[0,3],[1,2]]
    Output: "bacd"
    # Indices {0, 3} can be freely reordered; chars at those positions: {'d','b'} → sorted ['b','d'].
    # Indices {1, 2} can be freely reordered; chars: {'c','a'} → sorted ['a','c'].
    # Result: b a c d.
 
> Case 2:
    s = "dcab", pairs = [[0,3],[1,2],[0,2]]
    Output: "abcd"
    # All four indices are now in one class; sort all four chars.
 
> Case 3:
    s = "cba", pairs = [[0,1],[1,2]]
    Output: "abc"

Constraints

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

State design

Key insight: if indices i and j are linked (directly or transitively) by swap pairs, you can permute the characters at those indices in any order. Swaps generate the full symmetric group on the connected component.

So:

Union every pair into the same DSU class.
For each class, collect its indices and the characters at those indices.
Sort the characters ascending, then place them back at the (sorted) indices.

That puts the smallest available character at the smallest available index — lexicographically minimal.

Code

Analysis

Time: O((N + P) · α(N) + N log N) — DSU dominates the merging, the global sort cost is O(N log N) (sum of within-group sorts is ≤ N log N).
Space: O(N) for DSU and groups.

The “swaps generate the symmetric group” claim is worth dwelling on. With even 2 adjacent transpositions on 3 elements, you can produce all 6 permutations. The DSU class IS the orbit — every reachable rearrangement.

Same skin

Number of Connected Components — DSU into components, then count.
Accounts Merge — DSU on accounts indexed by emails, then group and sort.
Find the Town Judge — different shape, but also a “structural property of the equivalence class” question.

Satisfiability of Equality Equations Regions Cut By Slashes