Problem Description

You have a string s and an array called pairs containing index pairs. Each pair pairs[i] = [a, b] represents two positions (0-indexed) in the string where you can swap the characters.

The key rules are:

• You can perform swaps using any of the given pairs
• You can use each pair as many times as you want (including zero times)
• Your goal is to find the lexicographically smallest string possible after performing these swaps

For example, if you have the string "dcab" and pairs [[0,3],[1,2]], you can:

• Swap characters at positions 0 and 3 to get "bcad"
• Swap characters at positions 1 and 2 to get "bacd"
• Continue swapping to eventually reach "abcd" which is the lexicographically smallest

The important insight is that if position a can swap with b, and b can swap with c, then effectively a, b, and c form a group where characters can be rearranged freely among these positions. This transitivity means that within each connected group of indices, you can arrange the characters in any order.

The solution uses Union-Find (Disjoint Set Union) to:

1. Group all indices that are connected through the swap pairs
2. Collect all characters that belong to each group
3. Sort the characters in each group in ascending order
4. Place the smallest available character from each group at its corresponding position

The code accomplishes this by:

• Using find() function with path compression to identify the root of each connected component
• Grouping characters by their component root in dictionary d
• Sorting characters in reverse order (so we can use pop() to get the smallest)
• Building the result string by taking the smallest character from each position's component

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves pairs of indices that can be swapped, which forms a graph where indices are nodes and pairs represent edges between nodes that can exchange characters.

Is it a tree?

• No: The graph formed by the swap pairs is not necessarily a tree. It can have cycles (e.g., if pairs allow swaps like 0↔1, 1↔2, and 2↔0, forming a cycle).

Is the problem related to directed acyclic graphs?

• No: The graph is undirected (swaps are bidirectional) and may contain cycles.

Is the problem related to shortest paths?

• No: We're not looking for shortest paths between nodes. Instead, we need to find which indices can reach each other through a series of swaps.

Does the problem involve connectivity?

• Yes: The core insight is that indices form connected components - if index a can swap with b, and b can swap with c, then a, b, and c are all connected and their characters can be freely rearranged among these positions.

Disjoint Set Union (DSU)

• Yes: The flowchart leads us to DSU/Union-Find, which is perfect for finding connected components in the graph.

Conclusion: While the flowchart suggests DSU (which is indeed used in the solution), DFS could also be used as an alternative approach to find connected components. Both DFS and DSU can identify which indices belong to the same group, allowing us to sort characters within each group to achieve the lexicographically smallest string.

The DFS pattern would work by:

1. Starting from each unvisited index
2. Exploring all reachable indices through the swap pairs
3. Collecting all indices in the same connected component
4. Sorting the characters in that component and reassigning them

Intuition

The key insight comes from recognizing that swapping creates a transitive relationship. If we can swap positions a and b, and also swap b and c, then we can effectively move any character between positions a, b, and c through a series of swaps.

Think of it this way: imagine you have three cups labeled 0, 1, and 2, containing letters 'd', 'c', and 'a'. If you can swap cups 0↔1 and 1↔2, you can rearrange these letters in any order across the three cups. To get 'a' to position 0, you could swap 1↔2 (getting 'd', 'a', 'c'), then swap 0↔1 (getting 'a', 'd', 'c').

This means all indices that are connected through swap pairs form a group where characters can be freely rearranged. The problem then becomes:

1. Find all groups of connected indices
2. Within each group, we have complete freedom to arrange characters
3. To get the lexicographically smallest string, we should place the smallest available character at the earliest position

For example, if indices [0, 2, 4] form one group containing characters ['d', 'b', 'a'], we should arrange them as ['a', 'b', 'd'] to minimize the resulting string.

This naturally leads us to think about graph connectivity - we need to find which indices are "reachable" from each other through the swap relationships. Once we identify these connected components, the solution becomes straightforward: sort the characters in each component and assign them to positions in ascending order.

The Union-Find (DSU) data structure is perfect for this because it efficiently groups elements that are connected, while DFS could also traverse each component to achieve the same grouping effect.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Sorting patterns.

Solution Approach

The solution uses Union-Find (Disjoint Set Union) to identify connected components of indices that can swap characters with each other.

Step 1: Initialize Union-Find Structure

p = list(range(n))

We create a parent array where initially each index is its own parent, meaning each position starts as its own component.

Step 2: Build Connected Components

for a, b in pairs:
    p[find(a)] = find(b)

For each swap pair [a, b], we union the two indices by making them share the same root parent. The find() function with path compression ensures efficient lookups:

def find(x: int) -> int:
    if p[x] != x:
        p[x] = find(p[x])  # Path compression
    return p[x]

Step 3: Group Characters by Component

d = defaultdict(list)
for i, c in enumerate(s):
    d[find(i)].append(c)

We create a dictionary where each key is a component's root, and the value is a list of all characters belonging to that component. For example, if indices 0, 2, 4 are connected and contain 'd', 'b', 'a', they'll all be grouped under their common root.

Step 4: Sort Characters in Each Component

for i in d.keys():
    d[i].sort(reverse=True)

We sort characters in reverse order (largest first) so we can use pop() to efficiently get the smallest character. This is a performance optimization - pop() from the end of a list is O(1).

Step 5: Build the Result String

return "".join(d[find(i)].pop() for i in range(n))

For each position i from 0 to n-1:

• Find which component it belongs to using find(i)
• Pop the smallest character from that component's sorted list
• Add it to the result string

The algorithm ensures that within each connected component, characters are distributed to achieve the lexicographically smallest arrangement, while maintaining the constraint that characters can only be placed at indices within their component.

Time complexity: O(n log n + m * α(n)) where n is the string length, m is the number of pairs, and α is the inverse Ackermann function (practically constant). Space complexity: O(n) for the Union-Find structure and character groupings.

Example Walkthrough

Let's walk through the solution with a concrete example:

Input: s = "dcab", pairs = [[0,3],[1,2]]

Step 1: Initialize Union-Find We create a parent array p = [0, 1, 2, 3] where each index points to itself.

Step 2: Process Pairs to Build Components

• Process pair [0,3]:

  • find(0) = 0, find(3) = 3
  • Set p[0] = 3, so indices 0 and 3 are now connected
  • Parent array: p = [3, 1, 2, 3]

• Process pair [1,2]:

  • find(1) = 1, find(2) = 2
  • Set p[1] = 2, so indices 1 and 2 are now connected
  • Parent array: p = [3, 2, 2, 3]

Step 3: Group Characters by Component Now we iterate through each character and group them by their component root:

• Index 0 ('d'): find(0) = 3 → Add 'd' to component 3
• Index 1 ('c'): find(1) = 2 → Add 'c' to component 2
• Index 2 ('a'): find(2) = 2 → Add 'a' to component 2
• Index 3 ('b'): find(3) = 3 → Add 'b' to component 3

Our groups:

• Component 3: ['d', 'b'] (indices 0 and 3)
• Component 2: ['c', 'a'] (indices 1 and 2)

Step 4: Sort Characters in Each Component Sort each component's characters in reverse order:

• Component 3: ['d', 'b'] → ['d', 'b'] (already in reverse order)
• Component 2: ['c', 'a'] → ['c', 'a'] (already in reverse order)

Step 5: Build Result String For each position, pop the smallest character from its component:

• Position 0: find(0) = 3, pop from component 3 → 'b' (list becomes ['d'])
• Position 1: find(1) = 2, pop from component 2 → 'a' (list becomes ['c'])
• Position 2: find(2) = 2, pop from component 2 → 'c' (list becomes [])
• Position 3: find(3) = 3, pop from component 3 → 'd' (list becomes [])

Result: "bacd"

This makes sense because:

• Positions 0 and 3 can swap, so we put the smaller character 'b' at position 0 and 'd' at position 3
• Positions 1 and 2 can swap, so we put the smaller character 'a' at position 1 and 'c' at position 2

The resulting string "bacd" is the lexicographically smallest possible string we can achieve through the allowed swaps.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n + m × α(m))

The time complexity consists of two main components:

• The Union-Find operations: For each of the m pairs, we perform two find operations and one union operation. With path compression, each find operation takes O(α(m)) amortized time, where α is the inverse Ackermann function. This gives us O(m × α(m)) for processing all pairs.
• Sorting the characters: After grouping characters by their connected components, we sort each group. In the worst case, all n characters belong to the same component, requiring O(n × log n) time for sorting.
• The final string construction takes O(n) time as we pop from each sorted list once per character.

Therefore, the overall time complexity is O(n × log n + m × α(m)).

Space Complexity: O(n)

The space complexity includes:

• The parent array p of size n: O(n)
• The dictionary d storing all characters grouped by components: O(n) in total as it stores all n characters
• The output string construction: O(n)

The overall space complexity is O(n), where n is the length of the input string.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Union-Find Implementation Without Path Compression

Pitfall: Implementing the find operation without path compression can lead to degraded performance, turning the practically constant α(n) factor into O(n) in worst cases.

Incorrect Implementation:

def find_root(node: int) -> int:
    while parent[node] != node:
        node = parent[node]
    return node

Problem: This creates long chains where finding the root of deep nodes requires traversing many parent links, especially after multiple union operations.

Solution: Always use path compression to flatten the tree structure:

def find_root(node: int) -> int:
    if parent[node] != node:
        parent[node] = find_root(parent[node])  # Recursively compress path
    return parent[node]

2. Forgetting to Use find() When Accessing Components

Pitfall: Directly using the parent array values instead of calling find() when grouping or accessing characters.

Incorrect Code:

# Wrong: Using parent[i] directly
component_chars = defaultdict(list)
for index, char in enumerate(s):
    component_chars[parent[index]].append(char)  # Bug!

Problem: The parent array doesn't always point directly to the root. After unions, some nodes point to intermediate parents, not the actual root. This creates multiple separate groups for what should be a single connected component.

Solution: Always use find_root() to get the actual root:

component_chars[find_root(index)].append(char)  # Correct

3. Modifying the Original String Instead of Building a New One

Pitfall: Attempting to modify the string in-place or incorrectly tracking which characters have been used.

Incorrect Approach:

# Wrong: Trying to swap characters directly in the string
s = list(s)
for a, b in pairs:
    if s[a] > s[b]:
        s[a], s[b] = s[b], s[a]
return "".join(s)

Problem: This greedy approach doesn't consider the transitivity of swaps. Just because you can swap positions a and b doesn't mean you should do it immediately - the optimal character for position a might come from position c through a chain of swaps.

Solution: Group all connected positions first, then distribute the sorted characters optimally across the entire component.

4. Not Handling Empty Pairs Array

Pitfall: Assuming pairs array always has elements without checking.

Problem: When pairs is empty, no swaps are possible, and the original string should be returned. The code should handle this gracefully.

Solution: The current implementation naturally handles this case - when pairs is empty, each character remains in its own component, effectively returning the original string. However, for clarity, you could add an early return:

if not pairs:
    return s

5. Inefficient Character Removal from Sorted Lists

Pitfall: Using pop(0) to get the smallest character instead of sorting in reverse and using pop().

Incorrect Implementation:

# Inefficient: O(n) operation for each pop
component_chars[root].sort()  # Sort in ascending order
result.append(component_chars[root].pop(0))  # Remove from front

Problem: Removing from the front of a list is O(n) operation in Python, making the overall complexity worse.

Solution: Sort in reverse order and pop from the end (O(1) operation):

component_chars[root].sort(reverse=True)
result.append(component_chars[root].pop())  # Remove from end