medium

Smallest String With Swaps

Find the lexicographically smallest string reachable by swapping indices given as pairs.

1. Define the problem

Smallest String With Swaps

You are given a string s, and an array of pairs of indices pairs where pairsi = [ai, bi] indicates that you may swap the characters at indices ai and bi in s. You can swap indices any number of times. Return the lexicographically smallest string that s can be changed to after using the swaps. Union every swappable pair of indices into groups . Inside each group, any arrangement of characters is reachable, so sort each group and place the smallest characters at the group's smallest indices.

Constraints

  • 1 ≤ s.length ≤ 105
  • 0 ≤ pairs.length ≤ 105
  • 0 ≤ indices in pairs < s.length
  • s consists of lowercase English letters

Example

Inputs = "dcab", pairs = [[0,3],[1,2]]
Output"bacd"

Explanation Indices 0 and 3 form one group, indices 1 and 2 form another. Sorting each group's characters gives "bacd".

2. Visualize the solution

Union swappable indices, sort characters within each group

Union swappable indices, sort characters within each group
Statusunion

Union indices 0 and 3 from pair [0, 3].

What happens in this step

union(0, 3)
find(0) → 0   find(3) → 3
roots differ → union: parent[0] = 3
parent array: [0, 1, 2, 3] → [3, 1, 2, 3]

Indices 0 and 3 merge into one group, root 3 — their characters ('d' and 'b') can now be freely rearranged between them.
Step 1 of 3

Steps to visualize

  1. Union every pair of indices given in pairs.
  2. Group every index by its root — indices in the same group can trade characters freely.
  3. For each group, collect its characters, sort them, and hand the smallest ones to the smallest indices.
  4. Join the rewritten characters back into a string.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Union swappable indices, sort characters within each group
Statusunion

Union indices 0 and 3 from pair [0, 3].

What happens in this step

union(0, 3)
find(0) → 0   find(3) → 3
roots differ → union: parent[0] = 3
parent array: [0, 1, 2, 3] → [3, 1, 2, 3]

Indices 0 and 3 merge into one group, root 3 — their characters ('d' and 'b') can now be freely rearranged between them.
Step 1 of 3
4. Solution

Solution

solution.tsTypeScript
function smallestStringWithSwaps(s, pairs) {
  const n = s.length;
  const parent = Array.from({ length: n }, (_, i) => i);

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

  function union(a, b) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA !== rootB) {
      parent[rootA] = rootB;
    }
  }

  for (const [a, b] of pairs) {
    union(a, b);
  }

  const groups = new Map();
  for (let i = 0; i < n; i++) {
    const root = find(i);
    if (!groups.has(root)) groups.set(root, []);
    groups.get(root).push(i);
  }

  const result = s.split('');
  for (const indices of groups.values()) {
    const chars = indices.map((i) => s[i]).sort();
    indices.sort((a, b) => a - b);
    indices.forEach((index, position) => {
      result[index] = chars[position];
    });
  }

  return result.join('');
}
Time
O(n log n)
Space
O(n)
5. Test cases

Test cases

InputExpectedCovers
s = "dcab", pairs = [[0,3],[1,2]]"bacd"example from the docstring
s = "dcab", pairs = [[0,3],[1,2],[0,2]]"abcd"every index ends up in the same group, so the string becomes fully sorted
s = "cba", pairs = [[0,1],[1,2]]"abc"pairs chain together transitively into one group
s = "abc", pairs = []"abc"no swaps available, the string is unchanged
s = "ba", pairs = [[0,1]]"ab"smallest non-trivial case, a single swappable pair
s = "dcab", pairs = [[0,3],[3,0]]"bcad"a duplicated pair only affects the indices it names, leaving the rest untouched

Keep reading