What is the brute force approach and complexity for Smallest String With Swaps?

BFS over all strings reachable by swaps, keeping the smallest with time complexity O(N! · P · N) and space complexity O(N! · N).

What is the optimal approach and complexity for Smallest String With Swaps?

DSU over indices; write each group's sorted letters back into its indices in order with optimal time complexity O((N + P) · α + N log N) and space complexity O(N).

Smallest String With Swaps

Q: How do you identify the pattern for Smallest String With Swaps?

Look for key signals in the prompt: "swap the letters at pairs of indices, any number of times" indicates Each pair is an edge between two indices. Chains of edges make groups that can trade letters.; "smallest string" indicates Inside each group, the sorted letters go into the group's indices in increasing order..

Medium·LeetCode #1202 Pro OnlySlight Variation

LeetCode

Problem Statement

You get a string s and a list of index pairs. Each pair [a, b] lets you swap the letters at positions a and b. You may use these swaps as many times as you like, in any order.

Return the smallest string (in dictionary order) that you can reach.

Input

s: a string of lowercase letters. pairs: a list of [a, b] index pairs.

Output

The smallest string that any sequence of the allowed swaps can produce.

Example 1

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

Output: "bacd"

Swap indices 0 and 3: "bcad". Swap indices 1 and 2: "bacd". Nothing better is reachable with these two pairs.

Example 2

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

Output: "abcd"

The pairs (0, 3) and (0, 2) join indices 0, 2 and 3. The pair (1, 2) then joins index 1 to them, so all four indices form one group and their letters can be sorted freely.

Example 3

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

Output: "abc"

Index 0 can trade with 1, and 1 can trade with 2, so all three letters can be sorted.

Constraints

• 1 <= s.length <= 10^5
• 0 <= pairs.length <= 10^5
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s only contains lowercase English letters

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“swap the letters at pairs of indices, any number of times”

→ Each pair is an edge between two indices. Chains of edges make groups that can trade letters.

“smallest string”

→ Inside each group, the sorted letters go into the group's indices in increasing order.

Approach Complexity Ladder

Brute Force — explore every reachable stringO(N! · P · N)O(N! · N)

BFS over all strings reachable by swaps, keeping the smallest

Optimal — union the pairs, then sort each groupO((N + P) · α + N log N)O(N)

DSU over indices; write each group's sorted letters back into its indices in order

Brute Force Intuition

Start from s. From each string you reach, apply every allowed swap to get new strings. Keep a set of the strings already seen, so each one is expanded once. The answer is the smallest string the search reaches. Every swap can be undone by the same swap, so the search covers everything reachable.

Recognition rule for this sub-pattern:

"a equals b", "same owner", "can swap" — union them, then process each group together.

Remember this · Union-Find (DSU)

Trigger

Edges arrive one by one, "are these connected?", merge equivalent items, count components, extra edge creating a cycle.

Think

Am I repeatedly merging groups and asking whether two things are in the same group?

Key question

What are the elements, and what does it mean to union two of them?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Union-Find (DSU) translate into production architectures and low-level memory mechanics.

LLD Architecture