Smallest String With Swaps

📋

Problem

Imagine you have a string and a list of pairs of indices where you can swap characters any number of times. How can you rearrange the string to get the lexicographically smallest possible string?

Given a string s and an array of pairs of indices in the string, where each pair indicates that the characters at those indices can be swapped any number of times, return the lexicographically smallest string that can be obtained by performing zero or more swaps.

1 ≤ s.length ≤ 10^50 ≤ pairs.length ≤ 10^50 ≤ pairs[i][0], pairs[i][1] < s.lengths consists of lowercase English letters

Edge cases: Empty pairs array → string remains unchangedPairs that form one big connected component → entire string can be rearrangedPairs that form multiple disconnected components → sort each component independently

</>

IDE

def smallestStringWithSwaps(s: str, pairs: List[List[int]]) -> str:public String smallestStringWithSwaps(String s, List<List<Integer>> pairs)string smallestStringWithSwaps(string s, vector<vector<int>> pairs)function smallestStringWithSwaps(s, pairs)

def smallestStringWithSwaps(s, pairs):
    # Write your solution here
    pass

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        // Write your solution here
        return "";
    }
}

#include <vector>
#include <string>
using namespace std;

string smallestStringWithSwaps(string s, vector<vector<int>> pairs) {
    // Write your solution here
    return "";
}

function smallestStringWithSwaps(s, pairs) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: dcabNo swaps performed despite pairs allowing swaps; failed to group indices.✅ Implement union-find to group indices and sort characters within each group.

Wrong: acbdGreedy swapping only adjacent pairs once, missing full connected components.✅ Use union-find to find all connected indices and sort their characters.

Wrong: bacdIncorrect union-find implementation causing incomplete grouping.✅ Fix union-find parent and rank arrays and ensure path compression is applied.

Wrong: abdcSorting only partial groups or ignoring transitive connections.✅ Ensure union-find merges all connected indices including transitive pairs before sorting.

Wrong: Timeout or no outputBrute force or recursive swapping approach causing TLE on large inputs.✅ Implement efficient union-find with path compression and sort per connected component.

✓

Test Cases

Focus on handling edge cases like empty pairs and single character strings.

Watch out for greedy traps and ensure union-find merges all connected indices.

Optimize your solution to run efficiently on large inputs using union-find with path compression.

t1_01basic

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

Expected"bacd"

⏱ Performance - must finish in 2000ms

Indices 0 and 3 can be swapped, and indices 1 and 2 can be swapped. Group 1: indices {0,3} with chars 'd' and 'b' can be rearranged to 'b' and 'd'. Group 2: indices {1,2} with chars 'c' and 'a' can be rearranged to 'a' and 'c'. The final string is "bacd".

💡 Think about grouping indices that can be swapped using union-find.

💡 Sort characters within each connected component to get the smallest lexicographic order.

💡 Use union-find to find connected components, then sort and reassign characters per component.

Why it failed: Failed to group indices correctly or did not sort characters within groups. Fix by implementing union-find to identify connected components and sorting characters in each component before reassigning.

✓ Correctly grouped indices and sorted characters within each connected component.

t1_02basic

Input{"s":"cba","pairs":[[0,1],[1,2]]}

Expected"abc"

⏱ Performance - must finish in 2000ms

All indices are connected via pairs, so the entire string can be rearranged. Sorting all characters 'c','b','a' gives 'abc'.

💡 Check if all indices form one connected component.

💡 If so, sorting the entire string yields the smallest lexicographic string.

💡 Use union-find to confirm connectivity, then sort all characters in the component.

Why it failed: Incorrectly treated connected components as separate or failed to sort all characters in the connected component. Fix by ensuring union-find merges all connected indices and sorting their characters.

✓ Correctly identified single connected component and sorted all characters.

t2_01edge

Input{"s":"abc","pairs":[]}

Expected"abc"

⏱ Performance - must finish in 2000ms

No pairs to swap, so string remains unchanged.

💡 Consider the case when pairs array is empty.

💡 No swaps possible means output equals input.

💡 Return the original string if no pairs are given.

Why it failed: Output changed despite no pairs given. Fix by returning input string unchanged when pairs is empty.

✓ Correctly returned original string when no pairs are provided.

t2_02edge

Input{"s":"a","pairs":[]}

Expected"a"

⏱ Performance - must finish in 2000ms

Single character string with no pairs remains unchanged.

💡 Check behavior with single character string.

💡 No swaps possible with one character.

💡 Return the input string as is for single character input.

Why it failed: Output changed for single character input. Fix by handling single character input as base case returning input unchanged.

✓ Correctly handled single character input.

t2_03edge

Input{"s":"bbbaaa","pairs":[[0,1],[1,2],[3,4],[4,5]]}

Expected"bbbaaa"

⏱ Performance - must finish in 2000ms

Two connected components: indices {0,1,2} with 'b','b','b' and {3,4,5} with 'a','a','a'. All characters identical in each component, so sorting does not change string.

💡 Consider components with all identical characters.

💡 Sorting identical characters does not change order.

💡 Ensure sorting logic handles identical characters gracefully.

Why it failed: Incorrectly changed order of identical characters or failed to handle identical characters. Fix by sorting characters normally; identical characters remain unchanged.

✓ Correctly handled components with identical characters.

t3_01corner

Input{"s":"dcab","pairs":[[0,1],[1,2]]}

Expected"acdb"

⏱ Performance - must finish in 2000ms

Indices 0,1,2 form one connected component; index 3 alone. Sorting chars at indices {0,1,2} ('d','c','a') gives 'a','c','d'. Index 3 remains 'b'. Final string is 'acdb'.

💡 Beware of greedy approach that swaps only adjacent pairs once.

💡 Union-find groups all connected indices, not just direct pairs.

💡 Sort all characters in the connected component before reassigning.

Why it failed: Greedy approach swapping pairs once fails to find lex smallest string. Fix by using union-find to find all connected indices and sorting their characters.

✓ Correctly grouped connected indices and sorted characters to get lex smallest string.

t3_02corner

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

Expected"abcd"

⏱ Performance - must finish in 2000ms

All indices connected via pairs forming one component. Sorting all chars 'd','c','a','b' gives 'a','b','c','d'.

💡 Check if union-find merges all indices into one component.

💡 Sorting all characters in the single component yields lex smallest string.

💡 Ensure union-find merges transitive connections correctly.

Why it failed: Incorrectly treated connected components as separate or missed transitive connections. Fix by ensuring union-find merges all connected indices including transitive pairs.

✓ Correctly merged all indices into one component and sorted characters.

t3_03corner

Input{"s":"dcba","pairs":[[0,1],[1,2],[2,3]]}

Expected"abcd"

⏱ Performance - must finish in 2000ms

All indices connected forming one component. Sorting all chars 'd','c','b','a' gives 'a','b','c','d'.

💡 Beware off-by-one errors in union-find indexing.

💡 Ensure union-find parent and rank arrays are correctly initialized and updated.

💡 Sort all characters in the connected component after union-find grouping.

Why it failed: Off-by-one or indexing errors in union-find cause incorrect grouping. Fix by carefully implementing union-find with correct indexing and path compression.

✓ Union-find correctly groups all indices and sorting yields lex smallest string.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 with up to 100000 pairs. Efficient O(n log n + m α(n)) union-find solution must complete within 2 seconds.

💡 Use union-find with path compression and union by rank for efficiency.

💡 Avoid recursive or brute force approaches that try all swaps.

💡 Sorting characters per connected component should be done efficiently.

Why it failed: Brute force or naive solutions time out on large inputs. Fix by implementing union-find with path compression and sorting per connected component.

✓ Efficient union-find and sorting solution runs within time limits.

Practice

1. You are given a set of stones placed on a 2D grid. A move consists of removing a stone that shares either the same row or the same column with another stone. Which algorithmic approach guarantees finding the maximum number of stones that can be removed?

easy

A. Greedy approach removing stones one by one without tracking connectivity

B. Union-Find data structure connecting stones by rows and columns to find connected components

C. Dynamic programming to count stones based on row and column indices

D. Sorting stones by coordinates and removing duplicates

Solution

1. Step 1: Understand problem connectivity

   Stones can be removed if they share a row or column, which forms connected components of stones.

2. Step 2: Recognize union-find suitability

   Union-Find efficiently groups stones by connecting those sharing rows or columns, enabling counting of connected components.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Union-Find finds connected components in near-linear time [OK]

Hint: Connectivity by rows/columns -> union-find [OK]

Common Mistakes:

• Assuming greedy removal always works
• Trying DP without connectivity insight
• Sorting stones doesn't solve connectivity

2. You are given n computers and a list of connections where each connection connects two computers. You want to connect all computers with the minimum number of operations, where each operation can rewire an existing connection. Which algorithmic approach guarantees the optimal solution to determine the minimum operations needed or if it's impossible?

easy

A. Dynamic Programming to find the minimum spanning tree cost

B. Greedy approach that connects the most connected computers first

C. Union-Find (Disjoint Set Union) to count connected components and check redundant connections

D. Depth-First Search to find the longest path and rewire connections accordingly

Solution

1. Step 1: Understand problem requirements

   The problem requires connecting all computers with minimum operations by rewiring existing connections. This involves grouping nodes into connected components and counting redundant edges.

2. Step 2: Identify suitable algorithm

   Union-Find efficiently tracks connected components and redundant edges, enabling quick checks if the network can be connected and how many operations are needed.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Union-Find is the standard approach for connectivity and component counting [OK]

Hint: Union-Find tracks components and redundant edges efficiently [OK]

Common Mistakes:

• Thinking greedy or DFS alone can guarantee minimal rewiring
• Confusing MST with this problem
• Assuming DP applies directly

3. You are given a network of cities represented as an n x n matrix where isConnected[i][j] = 1 means city i is directly connected to city j. Your task is to find how many groups of cities are connected directly or indirectly. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that picks the city with the most connections first

B. Sorting cities by their connection counts and merging groups

C. Graph traversal using DFS or BFS to find connected components

D. Dynamic programming to count paths between cities

Solution

1. Step 1: Understand the problem as finding connected components in a graph

   The problem describes a graph where nodes are cities and edges represent direct connections. The goal is to find how many connected groups exist.

2. Step 2: Identify the algorithm that finds connected components efficiently

   DFS or BFS traversals can explore all nodes reachable from a starting node, marking them visited. Counting how many times you start a new traversal gives the number of connected components.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Connected components are found by graph traversal [OK]

Hint: Connected components -> DFS/BFS traversal [OK]

Common Mistakes:

• Thinking greedy or sorting can find connected components
• Confusing path counting with component counting

4. What is the time complexity of Kruskal's algorithm using union-find with path compression and union by size on a graph with n vertices and m edges?

medium

A. O(m log m + m α(n))

B. O(n^2)

C. O(m n)

D. O(m log n)

Solution

1. Step 1: Identify sorting cost

   Sorting edges takes O(m log m) time, which is equivalent to O(m log n) since m ≤ n^2.

2. Step 2: Analyze union-find operations

   Union-find operations take O(m α(n)) where α(n) is inverse Ackermann function, almost constant.

3. Step 3: Combine complexities

   The total complexity is O(m log n) dominated by sorting, as α(n) is negligible.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Sorting dominates, union-find nearly linear [OK]

Hint: Sorting edges + near-linear union-find cost dominates [OK]

Common Mistakes:

• Confusing α(n) with log n or n
• Assuming union-find is O(n) per operation
• Ignoring sorting cost or assuming O(m log n)

5. What is the time complexity of the optimal Union-Find algorithm with path compression and union by rank when finding the redundant connection in a graph with n edges?

medium

A. O(n²) because each union operation may traverse all nodes

B. O(n * α(n)) where α(n) is the inverse Ackermann function, nearly constant

C. O(n log n) due to sorting edges before union operations

D. O(n) because each edge is processed once without overhead

Solution

1. Step 1: Identify number of union/find operations

   There are n edges, each triggers at most one union and two finds.

2. Step 2: Analyze complexity of find with path compression and union by rank

   Each find/union operation runs in amortized O(α(n)) time, where α(n) is inverse Ackermann function, which grows extremely slowly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Union-Find with optimizations runs in near-linear time O(n * α(n)) [OK]

Hint: Inverse Ackermann function α(n) is almost constant [OK]

Common Mistakes:

• Assuming O(n²) due to nested loops
• Confusing sorting complexity with union-find
• Ignoring path compression benefits