Smallest String With Swaps
Asked at Goldman Sachs
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
How to Think About It
Simulating swaps greedily is a trap — you would need to reason about sequences of swaps.
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.
So the optimal string puts each component's characters in sorted order across that component's indices (also sorted).
Find components with union-find (or DFS). Group indices by root, sort each group's characters, and write them back to the sorted indices.
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).
What Trips People Up in Real Interviews
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.
Solution Code
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)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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.