Abstract / Summary

Group connected letters by swaps and sort each group to make the smallest possible string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 61% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Depth First Search
• Hash Table
• Sorting
• String
• Union Find

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of constructing the lexicographically smallest string that can be obtained by swapping characters at given index pairs. The core idea is to treat each index as a node in a graph, connect nodes that can be swapped directly, and then consider each connected component as a group of positions whose characters can be freely permuted. By sorting the characters inside each component and placing them back in order of appearance, the algorithm guarantees the smallest possible result.

Key Steps

Union-Find Initialization

The algorithm begins by creating a mapping from each index to itself, establishing each position as an independent set.

parent = { i: i for i in range(len(s)) }

This dictionary serves as the parent pointer array for the disjoint-set data structure.

Union Operation

For every pair of indices, the union function merges the two sets containing those indices. The function first finds the root of each index, then attaches the larger root to the smaller one. This deterministic choice reduces the height of the trees without requiring an explicit rank array.

def union(a, b):
    a = find(a)
    b = find(b)
    if a == b:
        return
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

Find with Path Compression

The find routine locates the root of a given index. If the index is not its own parent, the function recursively finds the root and updates the parent pointer along the way. This path compression step flattens the tree structure, ensuring that subsequent look-ups are fast.

def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])   # path compression
    return parent[a]

Building Connected Components

After processing all pairs, the algorithm iterates over each character in the original string, determines the component to which the character’s index belongs, and appends the character to a list associated with that component. A defaultdict(list) automatically creates a new list for each unseen component key.

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

Sorting Characters Within Each Component

Each component’s character list is sorted in ascending order, preparing the characters for placement in the final string. An auxiliary dictionary used tracks how many characters from each component have already been consumed.

used = {}
for g in groups:
    groups[g].sort()
    used[g] = 0

Constructing the Result String

The final pass walks through the original indices in order. For each index, the algorithm finds its component root, selects the next smallest unused character from that component’s sorted list, appends it to the result, and increments the usage counter for that component.

result = ""
for i in range(len(s)):
    index = find(i)
    result += groups[index][used[index]]
    used[index] += 1

The constructed result string is then returned.

Edge Cases Handled

When the input string is empty, the length of s is zero, resulting in an empty parent dictionary and an immediate return of an empty string after the final loop, which does not execute. If the pairs list is empty, no union operations occur, leaving each index in its own singleton component. The algorithm then sorts each single-character list (a no-op) and rebuilds the original string unchanged, which is the correct minimal result.

Duplicate pairs or pairs that reference the same index twice are safely ignored by the union logic because the find call will return identical roots, causing the early return in union. Self-referencing pairs (e.g., [i, i]) also result in no change, as the roots are equal.

Disconnected groups of indices are naturally separated because union operations only connect indices that appear together in a pair. Each disconnected component is processed independently, guaranteeing that characters are only swapped within their reachable set.

Performance Optimizations

The implementation leverages two classic disjoint-set optimizations. First, path compression in the find function collapses intermediate nodes directly to the root, dramatically reducing the cost of subsequent find calls. Second, the union step always attaches the larger root index to the smaller one, providing a simple heuristic that limits tree depth without the overhead of maintaining explicit rank information.

Sorting is performed once per component rather than repeatedly during reconstruction. By storing the sorted list and using an index pointer (used) to retrieve characters in order, the algorithm avoids costly list mutations such as pop(0), which would shift elements on each access. This approach yields a linear-time reconstruction phase after the initial sorting.

The use of a dictionary for parent and used, together with a defaultdict for grouping, ensures constant-time access to component data, contributing to overall efficiency.

Imagine you have a long string of letter blocks, like beads on a string, and you are allowed to swap the positions of some of these blocks based on a list of special connections. Think of the connections as little bridges between certain spots. Because those spots are connected, any letter in those spots can move to any other spot in the same group.

First, the code builds a map to remember which spots are connected to each other, forming little islands of connected positions. If two spots are connected to a third one, they all belong to the same island. After finding all these islands, the code looks at all the letters that live on each island. Because those letters can move freely anywhere within their own island, it is best to sort them so the smallest letters come first.

Finally, the code walks along the original string from start to finish. At each spot, it looks at which island that spot belongs to and picks the smallest letter available for that group. By picking the smallest possible letter for every spot, the final result becomes the best version of that string possible.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python				TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++		Java	Python	Go		Rust	TS
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fpdjsns	C++
	fsq	C++
	halfrost					Go
	JoshCrozier		JS
	lkwq007				Python
	suxrobGM						C#
	varunu28			Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality