{x}
blog image

Smallest String With Swaps

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^5
  • 0 <= pairs.length <= 10^5
  • 0 <= pairs[i][0], pairs[i][1] < s.length
  • s only contains lower case English letters.

Solution Explanation: Smallest String With Swaps

This problem asks to find the lexicographically smallest string that can be formed by swapping characters at indices specified in the pairs array. The key observation is that the swaps are transitive: if you can swap a with b, and b with c, then you can swap a with c. This suggests using a Union-Find algorithm to group indices that are effectively interchangeable.

Algorithm:

  1. Union-Find: We use a Union-Find data structure to group indices that can be swapped. Each group represents a set of indices whose characters can be arbitrarily rearranged. The find function in the code determines which group an index belongs to. We iterate through the pairs array, using union to merge groups whenever a swap is possible.

  2. Character Grouping: After building the Union-Find structure, we iterate through the input string s. For each character, we place it into the appropriate group (determined by find).

  3. Sorting and Reconstruction: Within each group, we sort the characters lexicographically (ascending order). Then, we reconstruct the string by taking the smallest character from each group and assigning it to the next index in the output string.

Time Complexity:

  • Union-Find: The union and find operations in Union-Find have amortized time complexity of nearly O(α(n)), where α is the inverse Ackermann function, which grows extremely slowly and is considered practically constant for all realistic input sizes.
  • Character Grouping and Sorting: Iterating through the string takes O(n) time. Sorting characters within each group takes O(n log n) in the worst case (if all indices are in one group).

Therefore, the overall time complexity is dominated by the sorting step: O(n log n).

Space Complexity:

  • Union-Find parent array: O(n) space.
  • Character groups: In the worst case, all indices could be in one group, resulting in O(n) space.

Therefore, the overall space complexity is O(n).

Code Examples (Python):

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        n = len(s)
        parent = list(range(n))
 
        def find(i):
            if parent[i] != i:
                parent[i] = find(parent[i])
            return parent[i]
 
        def union(i, j):
            root_i = find(i)
            root_j = find(j)
            parent[root_i] = root_j
 
        for i, j in pairs:
            union(i, j)
 
        groups = defaultdict(list)
        for i, char in enumerate(s):
            groups[find(i)].append(char)
 
        for group in groups.values():
            group.sort()
 
        result = list(s)
        for i, char in enumerate(s):
            root = find(i)
            result[i] = groups[root].pop(0)
 
        return "".join(result)

This Python code efficiently implements the Union-Find algorithm and character grouping to solve the problem. The other languages provide similar implementations with equivalent complexities. The core idea of Union-Find and sorting within groups remains consistent across all languages.