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.
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:
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.
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.
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:
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.
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.
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.
| 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 | — |
| 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 |
Smallest String With Swaps | Leetcode 1202 | Union Find Application | Live coding session • Coding Decoded • 7,594 views views
Watch 9 more video solutions →Practice Smallest String With Swaps with our built-in code editor and test cases.
Practice on FleetCode