Smallest String With Swaps

Smallest String With Swaps

What is this problem about?

The "Smallest String With Swaps" interview question gives you a string s and a list of pairs of indices. You can swap the characters at any of the given pairs any number of times. You need to find the lexicographically smallest string possible. This "Smallest String With Swaps coding problem" is a graph problem in disguise, as swapping indices (i, j) and (j, k) means you can move characters freely between i, j, and k.

Why is this asked in interviews?

Companies like Uber and Google ask this to test your ability to recognize connected components. Swapping pairs define edges in a graph. Any indices that are in the same connected component can have their characters rearranged in any order. The problem evaluates your proficiency with Union-Find (DSU) or DFS/BFS to group these indices and your ability to sort characters within those groups.

Algorithmic pattern used

This follows the "Union Find and Sorting interview pattern".

1. Use Union-Find to group all indices that are connected by the given swap pairs.
2. For each connected component:
   • Collect all the characters currently at those indices.
   • Sort the characters in ascending order.
   • Collect the indices and sort them in ascending order.
3. Place the sorted characters back into the sorted indices in the original string.

Example explanation

s = "dcba", pairs = [[0, 3], [1, 2]].

1. Components: {0, 3} and {1, 2}.
2. Component {0, 3}: Characters are 'd' and 'a'. Sorted: ['a', 'd']. Place 'a' at index 0 and 'd' at index 3.
3. Component {1, 2}: Characters are 'c' and 'b'. Sorted: ['b', 'c']. Place 'b' at index 1 and 'c' at index 2. Result: "abcd". If pairs = [[0, 1], [1, 2]], then {0, 1, 2} are all connected and can be sorted together.

Common mistakes candidates make

The most common mistake is thinking you can only swap the given pairs directly, missing the transitive property (swapping i-j and j-k allows i-k). Another error is not sorting both the characters and the indices for each component, which is necessary to correctly re-insert them into the string. Some candidates also struggle with the performance of building and iterating over the components.

Interview preparation tip

When you see "any number of swaps" between pairs, think of "Connected Components." This is a very common way to transform a string/array problem into a graph problem. This "Smallest String With Swaps interview question" is the textbook example of this transformation.