#1202

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Smallest String With Swaps

Find the lexicographically smallest string by swapping characters in given pairs of indices.

array hash table string depth first search breadth first search

Problem Statement

You are given a string s, and an array of pairs of indices pairs, where each pair [a, b] indicates that you can swap the characters at indices a and b of the string. Your goal is to return the lexicographically smallest string that can be obtained by repeatedly swapping characters as described.

The indices in pairs can be used any number of times, so it is crucial to find all indices that are connected, either directly or indirectly, through the given pairs. By sorting the characters within each connected component, you can obtain the smallest possible string.

Examples

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 details omitted.

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 details omitted.

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"

Example details omitted.

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 Approach

Union-Find Approach

Use a union-find data structure to group indices that are connected through the given swap pairs. Once the groups (connected components) are identified, for each group, sort the characters and assign them back to the string to get the lexicographically smallest result.

Depth-First Search (DFS) Approach

Treat the string indices as nodes in a graph and each pair in pairs as an undirected edge. Use DFS to explore all nodes in the same connected component. After finding all connected indices, sort the characters in those positions and place them back in the string to achieve the smallest string.

Breadth-First Search (BFS) Approach

Alternatively, use BFS to explore connected components, starting from each unvisited node. Once the connected component is found, sort the corresponding characters and reconstruct the string with the sorted characters.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used. For union-find, the time complexity is O(N * α(N)) where N is the length of the string, and α is the inverse Ackermann function. Sorting each connected component contributes an additional O(K log K), where K is the size of the component. For DFS/BFS, the complexity is O(N + M) where N is the number of nodes (characters) and M is the number of edges (pairs). The space complexity is O(N) due to the data structures used for the union-find or graph representation.

What Interviewers Usually Probe

Look for understanding of graph theory, particularly connected components.
Pay attention to how the candidate handles sorting within each connected component.
Check for optimization in the approach, especially in handling large inputs.

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort the characters within each connected component.
Failing to recognize that the problem is essentially about identifying connected components in a graph.
Not handling edge cases like no pairs or the minimum string length.

Follow-up variants

What if the swaps are limited to certain indices?
How would you optimize this problem for larger strings or more pairs?
Can this problem be solved with dynamic programming instead of graph traversal?

FAQ

What is the main algorithm used in Smallest String With Swaps?

The problem can be solved using union-find, DFS, or BFS to identify connected components and then sorting the characters within each component.

How do swaps in Smallest String With Swaps help minimize the string?

By swapping characters that are part of the same connected component, you can sort them lexicographically to obtain the smallest possible string.

What is the time complexity of the solution for Smallest String With Swaps?

The time complexity is O(N * α(N)) for union-find, or O(N + M) for DFS/BFS, where N is the number of characters and M is the number of pairs.

Can Smallest String With Swaps be solved without sorting?

No, sorting is essential to ensure the characters within each connected component are arranged lexicographically.

What is the graph theory application in Smallest String With Swaps?

The problem can be viewed as a graph where indices are nodes, and pairs are edges. The goal is to find connected components and sort the characters within them.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        n = len(s)
        p = list(range(n))
        for a, b in pairs:
            p[find(a)] = find(b)
        d = defaultdict(list)
        for i, c in enumerate(s):
            d[find(i)].append(c)
        for i in d.keys():
            d[i].sort(reverse=True)
        return "".join(d[find(i)].pop() for i in range(n))

Continue Practicing

#721 accounts merge #839 similar string groups #959 regions cut by slashes