Watch 10 video solutions for Smallest String With Swaps, a medium level problem involving Array, Hash Table, String. This walkthrough by Coding Decoded has 7,594 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: s = "dcab", pairs = [[0,3],[1,2]] Output: "bacd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[1] and s[2], s = "bacd"
Example 2:
Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]] Output: "abcd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[0] and s[2], s = "acbd" Swap s[1] and s[2], s = "abcd"
Example 3:
Input: s = "cba", pairs = [[0,1],[1,2]] Output: "abc" Explaination: Swap s[0] and s[1], s = "bca" Swap s[1] and s[2], s = "bac" Swap s[0] and s[1], s = "abc"
Constraints:
1 <= s.length <= 10^50 <= pairs.length <= 10^50 <= pairs[i][0], pairs[i][1] < s.lengths only contains lower case English letters.Problem Overview: You receive a string s and a list of index pairs that can be swapped any number of times. If two indices are connected directly or indirectly through swaps, their characters can be rearranged freely. The goal is to produce the lexicographically smallest string possible.
Approach 1: Union-Find (Disjoint Set Union) (O(n log n) time, O(n) space)
This approach groups indices that can reach each other through swaps. Use a Union Find structure to connect indices from each pair. After processing all pairs, every index belongs to a component representing positions that can be freely reordered. Iterate through the string and collect characters belonging to each component. Sort the characters inside each group, then rebuild the result by assigning the smallest available character to each index in that component. The union operations run nearly in constant time with path compression, but sorting characters inside components results in O(n log n) total time.
Approach 2: DFS for Connected Components (O(n log n) time, O(n) space)
Instead of Union-Find, treat the problem as a graph. Each index is a node, and each swap pair creates an undirected edge. Build an adjacency list and run Depth-First Search to discover connected components. For every unvisited index, start DFS and collect all reachable indices. Extract the corresponding characters from the string, sort them, and place them back in sorted order at the sorted list of indices. The DFS traversal takes O(n + p) where p is the number of pairs, while sorting characters within components dominates the runtime, giving overall O(n log n).
The key insight in both approaches is that swaps create connectivity groups. Within a group, positions can be rearranged arbitrarily. Once components are identified, the optimal strategy is greedy: place the smallest available character at the smallest index to minimize the final lexicographic order.
Recommended for interviews: Union-Find is usually the expected solution because it handles connectivity cleanly and scales well when the number of pairs is large. DFS shows the same understanding using graph traversal and is equally valid. Demonstrating the brute idea—grouping indices by connectivity—shows problem understanding, while implementing Union-Find efficiently demonstrates stronger algorithmic skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find (Disjoint Set Union) | O(n log n) | O(n) | Best general solution when many swap pairs exist and connectivity needs to be merged efficiently |
| DFS Connected Components | O(n log n) | O(n) | Useful when modeling swaps as a graph and performing traversal to collect components |