MediumArrayHash TableStringDepth-First SearchBreadth-First SearchUnion FindSortingUpdated Sep 2026

1202. Smallest String With Swaps

Asked at Goldman Sachs

Difficulty

Medium

Time

O(n log n + p * α(n))

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given a string s and a list of index pairs. Each pair [a, b] means you are allowed to swap the characters at positions a and b. You may use any pair as many times as you like, in any order.

Return the lexicographically smallest string you can reach. Lexicographically smallest means: compare strings character by character from the left, and the one with the smaller character at the first place they differ is smaller. So we want the smallest possible character at index 0, then the smallest possible at index 1, and so on.

The important rule: a swap is only allowed between positions that appear together in some pair. You cannot swap arbitrary positions. However, swaps chain together — if you can swap a with b, and b with c, then you can move characters freely among a, b and c.

Swaps link positions into groups

sdcab0123Pairs [0,3] and [1,2] give two separate groups: {0,3}and {1,2}sbacd0123Sort each group's characters and write them back:"bacd"
Each pair is an edge. Positions in the same connected group can exchange characters freely.

Constraints

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

Examples

Example 1
Inputs = "dcab", pairs = [[0,3],[1,2]]
Output"bacd"
WhyPositions 0 and 3 form one swap group, so their characters d and b can be reordered to b, d. Positions 1 and 2 form another group, so c and a become a, c. Putting them back in place gives "bacd".
Example 2
Inputs = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output"abcd"
WhyThe extra pair [0,2] links the two groups into one big group of all four positions. Now all four characters d, c, a, b can be arranged in any order, so we sort them to get "abcd".
Example 3
Inputs = "cba", pairs = [[0,1],[1,2]]
Output"abc"
WhyThe pairs connect 0-1 and 1-2, so positions 0, 1 and 2 are all in one group. Their characters c, b, a can be freely reordered, and sorting them gives "abc".

Asked At

1 companies
CompanyDifficulty
Goldman SachsMediumView all Goldman Sachs questions →

How to Think About It

1

Simulating swaps greedily is a trap — you would need to reason about sequences of swaps.

2

Key insight: treat indices as graph nodes and pairs as edges. Within a connected component, repeated swaps can produce any permutation of that component's characters.

3

So the optimal string puts each component's characters in sorted order across that component's indices (also sorted).

4

Find components with union-find (or DFS). Group indices by root, sort each group's characters, and write them back to the sorted indices.

5

Walkthrough: "dcab", pairs [[0,3],[1,2]]. Components {0,3} with d,b -> b,d, and {1,2} with c,a -> a,c. Result "bacd".

Optimal Approach

Step 1: Union every pair in a disjoint-set structure.
Step 2: Group indices by their root (indices are visited in increasing order, so each group is sorted).
Step 3: For each group, sort its characters and assign them to the group's indices in order.
Step 4: Return the joined string.

Time: O(n log n + p * α(n)). Space: O(n).

Union-find then sort per group

union every pairgroup indices by rootsort chars in each groupwrite chars back to indicesFour steps: build groups, then fix each groupindependentlygroup {0,3}db01Characters at indices 0 and 3 are d and b — sort themto b, dgroup {1,2}ca01Characters at indices 1 and 2 are c and a — sort themto a, csame group → any permutation is reachableso sort each group's characters
Union all pairs, collect indices by root, sort each group's characters, and place them back.
ComplexityTime O(n log n + p * α(n))Space O(n)Sorting the characters inside each group costs O(n log n) overall, and union-find operations cost almost O(1) each (α is the inverse Ackermann function).

What Trips People Up in Real Interviews

1

Applying swaps only when they immediately improve the string. Transitivity means indices that are never directly paired can still exchange characters.

2

Sorting characters but writing them to unsorted indices. Both the indices and the characters of a group must be in order.

3

Forgetting path compression and union by rank on large inputs — mention them even if the simple version passes.

4

Recursing for DFS on 10^5 nodes in Python without raising the recursion limit; union-find avoids it.

Solution Code

O(n log n + p * α(n)) time
def smallestStringWithSwaps(s, pairs):
    parent = list(range(len(s)))

    def find(x):
        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(len(s)):
        groups.setdefault(find(i), []).append(i)
    res = list(s)
    for idx in groups.values():
        chars = sorted(s[i] for i in idx)
        for i, c in zip(idx, chars):
            res[i] = c
    return ''.join(res)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Smallest String With Swaps problem?

Smallest String With Swaps gives you a string and a list of index pairs you may swap any number of times, and asks for the lexicographically smallest string you can reach. The key realization is that swaps are transitive: within a connected group of indices, you can arrange the characters in any order.

How do you solve Smallest String With Swaps?

The optimal approach runs in O(n log n + p * α(n)) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Smallest String With Swaps?

Smallest String With Swaps is asked at Goldman Sachs. It is a medium difficulty problem.

What are common mistakes on Smallest String With Swaps?
  • Applying swaps only when they immediately improve the string. Transitivity means indices that are never directly paired can still exchange characters.
  • Sorting characters but writing them to unsorted indices. Both the indices and the characters of a group must be in order.
  • Forgetting path compression and union by rank on large inputs — mention them even if the simple version passes.
  • Recursing for DFS on 10^5 nodes in Python without raising the recursion limit; union-find avoids it.