Smallest String with Swaps

Explanation & Solution

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.

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

Output: "bacd"

Explanation: Swap s[0] and s[3] → "bcad". Swap s[1] and s[2] → "bacd".

Constraints

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

Approach

Union Find pattern

1. Initialize Union Find

Create a parent array where each index is its own parent
Track rank for union by rank optimization

2. Union All Swap Pairs

For each pair [a, b], union indices a and b
If you can swap a↔b and b↔c, you can transitively rearrange a, b, c in any order

3. Group Indices by Component

Find the root of each index and group indices by their root
Each group contains all indices whose characters can be freely rearranged

4. Sort Characters Within Each Group

For each group, collect the characters at those indices
Sort both the characters and the indices
Place the smallest character at the smallest index within the group

5. Build Result

Join the result array into a string

Key Insight

If indices are transitively connected by swap pairs, their characters can be arranged in any order
Union Find identifies these connected components efficiently
Within each component, sorting characters and placing them at sorted positions gives the lexicographically smallest result

Time

O(n log n) dominated by sorting

Space

O(n)

Visualization

Input:

[d, c, a, b]

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

Most Stones Removed with Same Row or Column

Regions Cut by Slashes