Smallest String With Swaps

▶

Steps

setup

Initialize Union-Find Structure

Create a UnionFind instance for all indices of the string 'dcab'. Each index is initially its own parent, representing separate sets.

💡 This initialization sets up the foundation for grouping indices that can be swapped. Each index starts isolated.

Line:

uf = UnionFind(n)

💡 Each index is initially in its own group, so no swaps are possible yet.

expand

Union indices 0 and 3

Perform union operation on indices 0 and 3, connecting their sets. This means characters at these indices can be swapped.

💡 Union merges two sets, allowing swaps between their indices. This step connects 'd' and 'b'.

Line:

uf.union(0, 3)

💡 Indices 0 and 3 now belong to the same group, enabling swaps between these positions.

expand

Union indices 1 and 2

Perform union operation on indices 1 and 2, connecting their sets. This means characters at these indices can be swapped.

💡 This union connects 'c' and 'a', forming another group for swaps.

Line:

uf.union(1, 2)

💡 Indices 1 and 2 now belong to the same group, enabling swaps between these positions.

traverse

Find root of index 0

Find the root parent of index 0 to identify its group. This root will be used to group characters.

💡 Finding root parent identifies which group an index belongs to.

Line:

root = uf.find(0)

💡 Index 0 belongs to the group with root 0 (or possibly 3 depending on union implementation).

fill_cells

Add character 'd' at index 0 to group heap

Add character 'd' from index 0 to the min-heap of its group identified by root 0.

💡 Grouping characters by their connected component allows sorting within groups.

Line:

heapq.heappush(groups[root], s[i])

💡 Characters in the same group can be rearranged freely.

traverse

Find root of index 1

Find the root parent of index 1 to identify its group for character grouping.

💡 Each index's root determines which group its character belongs to.

Line:

root = uf.find(1)

💡 Index 1 belongs to the group with root 1 (or 2 depending on union).

fill_cells

Add character 'c' at index 1 to group heap

Add character 'c' from index 1 to the min-heap of its group identified by root 1.

💡 Characters are collected in heaps to allow efficient retrieval of smallest characters.

Line:

heapq.heappush(groups[root], s[i])

💡 Group heap now contains 'c' for group 1.

traverse

Find root of index 2

Find the root parent of index 2 to identify its group for character grouping.

💡 Index 2's root determines which group its character 'a' belongs to.

Line:

root = uf.find(2)

💡 Index 2 belongs to the same group as index 1.

fill_cells

Add character 'a' at index 2 to group heap

Add character 'a' from index 2 to the min-heap of its group identified by root 1.

💡 Adding 'a' to the heap with 'c' allows sorting characters within the group.

Line:

heapq.heappush(groups[root], s[i])

💡 Group heap for root 1 now contains ['a', 'c'], ready for smallest character extraction.

traverse

Find root of index 3

Find the root parent of index 3 to identify its group for character grouping.

💡 Index 3's root determines which group its character 'b' belongs to.

Line:

root = uf.find(3)

💡 Index 3 belongs to the same group as index 0.

fill_cells

Add character 'b' at index 3 to group heap

Add character 'b' from index 3 to the min-heap of its group identified by root 0.

💡 Adding 'b' to the heap with 'd' allows sorting characters within the group.

Line:

heapq.heappush(groups[root], s[i])

💡 Group heap for root 0 now contains ['b', 'd'], ready for smallest character extraction.

reconstruct

Reconstruct character for index 0

Find root of index 0 and pop the smallest character from its group's heap to place at index 0 in the result.

💡 Extracting smallest characters from heaps ensures lexicographically smallest string.

Line:

smallest_char = heapq.heappop(groups[root])

💡 Index 0 gets character 'b', the smallest in its group.

reconstruct

Reconstruct character for index 1

Find root of index 1 and pop the smallest character from its group's heap to place at index 1 in the result.

💡 Continuing to extract smallest characters maintains lex order.

Line:

smallest_char = heapq.heappop(groups[root])

💡 Index 1 gets character 'a', the smallest in its group.

reconstruct

Reconstruct character for index 2

Find root of index 2 and pop the smallest character from its group's heap to place at index 2 in the result.

💡 Extracting next smallest character from the same group heap.

Line:

smallest_char = heapq.heappop(groups[root])

💡 Index 2 gets character 'c', the next smallest in its group.

reconstruct

Reconstruct character for index 3

Find root of index 3 and pop the smallest character from its group's heap to place at index 3 in the result.

💡 Extracting last character from the group heap completes the string.

Line:

smallest_char = heapq.heappop(groups[root])

💡 Index 3 gets character 'd', the last remaining in its group.

from typing import List
import heapq

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # STEP 1
        self.rank = [0]*n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # STEP 4,6,8,10
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)  # STEP 2,3
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[ry] < self.rank[rx]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        n = len(s)
        uf = UnionFind(n)  # STEP 1
        for x, y in pairs:
            uf.union(x, y)  # STEP 2,3
        groups = {}
        for i in range(n):
            root = uf.find(i)  # STEP 4,6,8,10
            if root not in groups:
                groups[root] = []
            heapq.heappush(groups[root], s[i])  # STEP 5,7,9,11
        res = []
        for i in range(n):
            root = uf.find(i)  # STEP 12,13,14,15
            smallest_char = heapq.heappop(groups[root])
            res.append(smallest_char)
        return ''.join(res)

if __name__ == '__main__':
    sol = Solution()
    print(sol.smallestStringWithSwaps("dcab", [[0,3],[1,2]]))  # Output: "bacd"

📊

Smallest String With Swaps - Watch the Algorithm Execute, Step by Step

Watching each union operation and the grouping of indices reveals how connected components form, which is key to understanding how swaps can reorder characters within these groups.

Visiting: none

0

1

2

3

Visiting: 0

Edge: 0 → 3

0

1

2

3

Visiting: 1

Edge: 1 → 2

0

1

2

3

Visiting: 0

0

1

2

3

Visiting: 0

0

1

2

3

Visiting: 1

0

1

2

3

Visiting: 1

0

1

2

3

Visiting: 2

0

1

2

3

Visiting: 2

0

1

2

3

Visiting: 3

0

1

2

3

Visiting: 3

0

1

2

3

Visiting: 0

0

1

2

3

Visiting: 1

0

1

2

3

Visiting: 2

0

1

2

3

Visiting: 3

0

1

2

3

Key Takeaways

✓ Union-Find groups indices that can be swapped, revealing connected components.

This grouping is not obvious from code alone but is clear when watching union operations merge sets.

✓ Characters within each connected component are collected and sorted using min-heaps.

Seeing characters grouped and sorted visually helps understand how swaps reorder characters locally.

✓ Reconstructing the string by extracting smallest characters from each group's heap ensures lexicographically smallest result.

The step-by-step extraction clarifies how the final string is built from local minimums.

Practice

1. You are given a list of user accounts, each with a username and multiple email addresses. Some accounts may belong to the same user if they share at least one email address. Which algorithmic approach best guarantees merging all accounts belonging to the same user efficiently?

easy

A. Greedy approach that merges accounts by comparing usernames only

B. Dynamic programming to find the longest common subsequence of emails

C. Brute force nested loops checking every pair of accounts for email overlap

D. Union-Find data structure to group emails that appear in multiple accounts

Solution

1. Step 1: Understand the problem structure

   The problem requires grouping accounts by shared emails, which naturally forms connected components in a graph where emails are nodes.

2. Step 2: Identify the suitable algorithm

   Union-Find efficiently merges sets of emails that belong to the same user, handling multiple overlaps without redundant comparisons.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Union-Find is the classic pattern for merging overlapping sets [OK]

Hint: Accounts merge is a connected components problem [OK]

Common Mistakes:

• Merging by username only misses shared emails
• Brute force is too slow for large inputs

2. What is the time complexity of the optimal union-find based solution for the Accounts Merge problem, where N is the number of accounts and M is the maximum number of emails per account?

medium

A. O(N^2 * M) because each account is compared with every other

B. O(N * M^2) due to nested loops over emails

C. O(N * M * α(N * M)) where α is the inverse Ackermann function

D. O(N * M log (N * M)) due to sorting emails after union

Solution

1. Step 1: Identify union-find operations cost

   Union-find operations (union/find) run in nearly O(1) amortized time, specifically O(α(N*M)) per operation.

2. Step 2: Count total operations

   We perform union operations for each email in each account, totaling O(N*M) unions and finds.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Union-find with path compression yields almost linear time [OK]

Hint: Union-find nearly linear with inverse Ackermann factor [OK]

Common Mistakes:

• Confusing sorting cost with union-find cost
• Assuming quadratic due to nested loops

3. Examine the following buggy DFS code for counting provinces. Which line contains the subtle bug that can cause incorrect results or infinite recursion?

medium

A. Line 4: visited[city] = True

B. Line 2: for neighbor in graph[city]:

C. Line 1: def dfs(city: int):

D. Line 3: if not visited[neighbor]:

Solution

1. Step 1: Understand DFS visit marking

   Visited nodes must be marked before recursive calls to avoid revisiting and infinite loops.

2. Step 2: Identify bug in visit marking

   Marking visited after recursion causes repeated visits and possible infinite recursion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited marking must be before recursion to prevent cycles [OK]

Hint: Visited marking after recursion causes infinite loops [OK]

Common Mistakes:

• Marking visited too late
• Confusing visited marking with neighbor iteration

4. Examine the following buggy code snippet for the optimal solution. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line 2: Sorting edges by type descending

B. Line 16: Checking if both Alice and Bob are fully connected

C. Line 9: Using union-find union for type 3 edges

D. Line 6: Not adjusting node indices from 1-based to 0-based

Solution

1. Step 1: Identify indexing issue

   Input edges use 1-based node indices, but union-find expects 0-based. Missing adjustment causes wrong unions or runtime errors.

2. Step 2: Confirm other lines are correct

   Sorting edges, union calls, and connectivity checks are correct; only indexing is buggy.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing "u -= 1; v -= 1" causes incorrect unions [OK]

Hint: Check if node indices are adjusted before union-find calls [OK]

Common Mistakes:

• Ignoring 1-based to 0-based index conversion
• Misusing union-find union return value
• Skipping connectivity check for both users

5. Suppose you want to find a minimum spanning forest (MST for each connected component) in a graph that may be disconnected. Which modification to the Kruskal's algorithm with union-find is necessary to correctly handle this scenario?

hard

A. Remove the break condition and process all edges to connect all components separately

B. Use DFS to find connected components first, then run Kruskal on each separately

C. Stop after adding n-1 edges, as usual, since MST covers all nodes

D. Add edges only if they connect nodes in the same component to avoid cycles

Solution

1. Step 1: Understand MST vs MST forest

   In disconnected graphs, MST is a forest; stopping after n-1 edges assumes connectivity, which may not hold.

2. Step 2: Modify Kruskal to process all edges

   Removing the break condition allows union-find to connect all components separately, building MST forest.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Process all edges to cover disconnected components [OK]

Hint: Don't stop early if graph is disconnected; build MST forest instead [OK]

Common Mistakes:

• Stopping early assuming graph is connected
• Running DFS first adds unnecessary complexity
• Misusing union-find to connect nodes in same component