Smallest String With Swaps - Solution & Explanation
Problem Statement
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.lengthsonly contains lower case English letters.
Approach Overview
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 1: Union-Find (Disjoint Set Union)
In this approach, we use the Union-Find (also known as Disjoint Set Union, DSU) data structure. This structure helps efficiently group indices that can be swapped. Once we group the indices, we can individually sort characters in each connected component to ensure the smallest lexicographical order.
Steps:
- Initialize a Union-Find structure for the indices of the string.
- Iterate through each pair in the 'pairs' array and perform union operations on the indices.
- Create a mapping from root parent to all indices in that connected component by leveraging the 'find' operation.
- For each component of indices, gather and sort the characters, then place them back in the original string positions according to indices mapping.
The provided Python code defines a UnionFind class to help manage connected components through union and find operations. The 'smallestStringWithSwaps' function makes use of this class to find connected components from the given pairs. For each component, it sorts the characters and places them back in the string res according to their indices.
Complexity
Time Complexity: O(M * α(N) + NlogN), where M is the number of pairs, α is the inverse Ackermann function (very small constant), and N is the length of the string.
Space Complexity: O(N) for the union-find structure and the character groups.
Approach 2: DFS for Connected Components
This approach utilizes Depth-First Search (DFS) to find connected components in a graph that represents swap pairs. Each unique character component is individually sorted to form the smallest possible string.
Steps:
- Build an adjacency list for the graph using the pairs provided.
- For each index not yet visited, perform a DFS to discover all connected components.
- Gather all indices in a connected component, sort the characters corresponding to these indices, and re-position them in the string.
The Java solution uses an adjacency list to represent the swap pairs as a graph. It performs a DFS from each unvisited node to discover all nodes connected to it, gathering indices and corresponding characters. These gathered components are sorted to ensure lexicographically smallest entries at their respective indices.
Complexity
Time Complexity: O(N + M + C log C), where N is the number of nodes, M is the number of edges in the graph (pairs), and C is the size of the largest component.
Space Complexity: O(N + M), as we store the adjacency graph and visit flags.
Approach 3: Union-Find
We notice that the index pairs have transitivity, i.e., if a and b can be swapped, and b and c can be swapped, then a and c can also be swapped. Therefore, we can consider using a union-find data structure to maintain the connectivity of these index pairs, and sort the characters belonging to the same connected component in lexicographical order.
Finally, we traverse the string. For the character at the current position, we replace it with the smallest character in the connected component, then remove this character from the connected component, and continue to traverse the string.
The time complexity is O(n times log n + m times \alpha(m)), and the space complexity is O(n). Here, n and m are the length of the string and the number of index pairs, respectively, and \alpha is the inverse Ackermann function.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Union-Find (Disjoint Set Union) | Time Complexity: O(M * α(N) + NlogN), where M is the number of pairs, α is the inverse Ackermann function (very small constant), and N is the length of the string. Space Complexity: O(N) for the union-find structure and the character groups. |
| DFS for Connected Components | Time Complexity: O(N + M + C log C), where N is the number of nodes, M is the number of edges in the graph (pairs), and C is the size of the largest component. Space Complexity: O(N + M), as we store the adjacency graph and visit flags. |
| Union-Find | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Smallest String With Swaps | Leetcode 1202 | Union Find Application | Live coding session • Coding Decoded • 7,861 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Smallest String With Swaps easy or hard?
Smallest String With Swaps Python/Java solution
How to solve Smallest String With Swaps in O(n)?
What is the best approach for Smallest String With Swaps?
Is Smallest String With Swaps asked at Google/Amazon/Meta?
What data structure is used in Smallest String With Swaps?
What is the time complexity of Smallest String With Swaps?
Ready to solve this problem?
Practice Smallest String With Swaps with our built-in code editor and test cases.
Practice on FleetCode