Abstract / Summary

Given a string and a set of swap operations, find the lexicographically smallest string possible after performing any number of swaps in any order.

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 79% (100k+ submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Depth First Search
• Enumeration
• String

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 defines a class Solution with a single public method findLexSmallestString. The method receives a numeric string s and two integers a and b. It explores all strings reachable by repeatedly applying two operations: adding a to every digit in odd-positioned indices (0-based) with wrap-around modulo 10, and rotating the string to the right by b positions. The goal is to return the lexicographically smallest string among all reachable configurations.

The algorithm uses depth-first recursion combined with a global seen set to avoid revisiting already processed strings. By exhaustively traversing the state space while caching results, it guarantees that every distinct reachable string is examined exactly once, and the final answer is obtained by selecting the minimum element from the seen collection.

Precomputation of Digit Transformations

Before any recursion begins, the code builds a dictionary that maps each character digit to its value after the addition operation. This lookup table eliminates the need for repeated arithmetic and string conversion inside the recursive loop.

odd = {}
for i in range(10):
    odd[str(i)] = str((i + a) % 10)

The table odd contains ten entries, one for each possible digit, allowing constant-time retrieval of the transformed digit during the shift step.

Recursive Exploration

A nested function deeper encapsulates the depth-first search. The first action inside deeper is a membership test against the seen set. If the current string x has already been processed, the function returns immediately, preventing infinite loops caused by cycles in the operation graph.

if x in seen:
    return
seen.add(x)

Rotation Step

The rotation operation moves the last b characters to the front. The code constructs the rotated string with slicing and immediately recurses on the result.

deeper(x[-b:] + x[:-b])

Because the rotation is deterministic and reversible, the recursion will eventually revisit previously seen configurations, at which point the early-exit guard stops further expansion.

Shift (Addition) Step

The shift operation iterates over all odd indices (1, 3, 5, …) of the current string. For each such position, the character is replaced by its precomputed counterpart from the odd dictionary. The updated string is built by concatenating three slices: the prefix up to the index, the transformed digit, and the suffix after the index.

for i in range(1, len(x), 2):
    x = x[:i] + odd[x[i]] + x[i+1:]

After the loop finishes, the fully transformed string is passed to deeper for further exploration.

deeper(x)

Termination and Result

The initial call deeper(s) launches the search from the input string. Once the recursion unwinds, the seen set contains every distinct string reachable through any sequence of the two operations. The final line selects the lexicographically smallest element using Python’s built-in min.

return min(seen)

Because seen is a Python set, insertion and membership checks are performed in average constant time, ensuring that the algorithm does not waste effort on duplicate states.

Edge Cases Handled

The implementation gracefully handles the situation where b equals the length of the string. In that case the rotation slice x[-b:] yields the entire string and x[:-b] yields an empty prefix, resulting in the original string; the early-exit guard then prevents redundant recursion.

When a is zero, the precomputed dictionary maps each digit to itself, and the shift loop effectively leaves the string unchanged. The algorithm still explores the rotation space, and the early-exit condition again avoids infinite recursion.

If the input string consists of a single character, the range range(1, len(x), 2) produces no indices, so the shift loop is skipped. The rotation of a single-character string also yields the same string, and the recursion terminates after the first membership check.

The code also works correctly when b is larger than the string length because Python slicing automatically wraps around: x[-b:] returns the appropriate suffix and x[:-b] returns the complementary prefix. This implicit handling eliminates the need for explicit modulo arithmetic on the rotation offset.

Performance Optimizations

The most noticeable optimization is the precomputation of the digit transformation table. By converting the arithmetic (i + a) % 10 into a dictionary lookup, the inner loop that processes odd positions avoids repeated integer conversion and modulo operations, reducing per-iteration overhead.

Caching via the seen set is another key optimization. Without this guard, the recursive calls would revisit the same configurations exponentially many times, leading to severe slowdown. The set ensures that each unique string is processed exactly once, turning the potentially exponential state space into a linear traversal relative to the number of distinct reachable strings.

The use of Python string slicing to perform both rotation and digit replacement creates new string objects without mutating the original. Although this incurs allocation cost, it simplifies the logic and leverages the highly optimized C implementation of slicing, which is faster than manual character-by-character manipulation.

Finally, the recursion depth is bounded by the number of distinct reachable strings. Because each recursive call either rotates or shifts the string, and both operations are deterministic, the depth never exceeds the size of seen. This implicit bound prevents stack overflow for typical input sizes encountered in practice.

Imagine a magical string made of little number beads. The goal is to make these numbers look as small as possible, like counting up to the tiniest number you can find. To do this, there are two secret buttons to push. The first button slides all the beads to the side, almost like spinning a bicycle wheel so the end beads move to the front. The second button picks out the beads at special spots and makes their numbers grow by adding a secret amount to them. If the number gets too big, it wraps back around to zero, just like how the clock circles back to one after the hour of twelve.

Because there are many ways to push these buttons, the path can get a bit twisty. To make sure no time is wasted, the computer keeps a list of every version of the bead string that it has already seen. Every time the computer tries a new move, it checks this list first. If the computer has already seen that version of the string, it stops and goes back to try something else. By trying every single combination of spinning the beads and changing their values, the computer collects every possible string. At the very end, it looks through all the strings gathered in that list and picks the one that starts with the smallest digit, just like finding the smallest number in a toy box.

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

not analyzed yet

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++	Python		Java			TS
	WalkCCC	C++			Java
	leetcode.ca	C++	Python		Java		Go	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fsq	C++
	haoel	C++
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM					C#
	trung-hn		Python
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
wisdompeak	C++
withaarzoo	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