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.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.
C++
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.
C#
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 | 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. |
Minimum Number of Swaps to Make String Balanced - Leetcode 1963 Weekly Contest - Python • NeetCode • 47,493 views views
Watch 9 more video solutions →Practice Smallest String With Swaps with our built-in code editor and test cases.
Practice on FleetCode