How do you solve Smallest String With Swaps on LeetCode?

Smallest String With Swaps (LeetCode #1202) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Understanding the problem as a graph helps in visualizing the connections between indices.

What is the brute force solution for Smallest String With Swaps?

The brute force approach for Smallest String With Swaps is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible strings by performing swaps as indicated by the pairs. This means we would explore every combination of swaps to find the lexicographically smallest string. The optimal Optimal Solution approach improves this to O(n log n).

What are the interview tips for Smallest String With Swaps?

Always clarify how swaps can be performed and what that implies for the structure of the string. Think about how to represent the problem — using graphs can simplify complex relationships. Practice DFS and Union-Find techniques, as they are common in problems involving connectivity.

What are common mistakes when solving Smallest String With Swaps?

Failing to recognize that swaps can be treated as connections in a graph. Not handling all connected components properly during DFS or Union-Find.

#1202

Smallest String With Swaps

Medium

ArrayHash TableStringDepth-First SearchBreadth-First SearchUnion-FindSortingGraph Traversal (DFS, BFS)Union-FindSorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

The optimal solution treats the problem as a graph where each index is a node and each pair represents an edge. By finding connected components, we can sort the characters in those components to get the smallest possible string.

⚙️

Algorithm

4 steps

1Step 1: Build a graph using the pairs where each index is a node.
2Step 2: Use Depth-First Search (DFS) or Union-Find to find all connected components.
3Step 3: For each connected component, collect the characters and sort them.
4Step 4: Place the sorted characters back into their original positions in the string.

solution.py30 lines

1# Full working Python code
2from collections import defaultdict
3
4def smallestStringWithSwaps(s, pairs):
5    graph = defaultdict(list)
6    for a, b in pairs:
7        graph[a].append(b)
8        graph[b].append(a)
9    visited = [False] * len(s)
10    s = list(s)
11    
12    def dfs(node, component):
13        visited[node] = True
14        component.append(node)
15        for neighbor in graph[node]:
16            if not visited[neighbor]:
17                dfs(neighbor, component)
18
19    for i in range(len(s)):
20        if not visited[i]:
21            component = []
22            dfs(i, component)
23            chars = sorted(s[j] for j in component)
24            for j, char in zip(sorted(component), chars):
25                s[j] = char
26
27    return ''.join(s)
28
29# Example usage
30print(smallestStringWithSwaps('dcab', [[0,3],[1,2]]))

ℹ

Complexity note: The time complexity is dominated by the sorting step for each connected component, which is O(n log n) when considering all components together. The space complexity accounts for the graph representation and visited array.

1Understanding the problem as a graph helps in visualizing the connections between indices.
2Sorting characters in connected components guarantees the smallest lexicographical order.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.