Abstract / Summary

Find the earliest position where swapping with a later smaller character makes the string lexicographically smallest.

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

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 single method getSmallestString that receives a string s and returns the lexicographically smallest string obtainable by either leaving the input unchanged or performing a single adjacent-character swap under specific conditions. The core logic is expressed in a compact list comprehension combined with Python’s built-in min function.

Key Steps

The method follows a three-stage process:

1. Base candidate creation - The original string s is placed as the first element of a list that will hold all possible candidates.

   [s]

2. Conditional swap generation - A list comprehension iterates over every index i from 1 to len(s) - 1. For each position it checks two predicates:

   • The character at position i must be strictly smaller than the character immediately to its left (s[i] < s[i-1]).
   • The sum of the integer values of the two characters must be even, expressed through the bitwise expression 0 == 1 & (int(s[i]) + int(s[i-1])).

   When both predicates hold, a new string is built by swapping the two adjacent characters while preserving the rest of the original sequence:

   s[:i-1] + s[i] + s[i-1] + s[i+1:]

   The comprehension therefore yields a collection of all strings that result from a single qualifying swap.

3. Selection of the smallest string - The min function receives the concatenated list of the original string and all generated swaps. It returns the element that is smallest according to Python’s default lexicographic ordering for strings.

   return min([s] + [ ... for i in range(1, len(s)) if ... ])

Edge Cases Handled

When the input string has length zero or one, the range used in the comprehension (range(1, len(s))) produces no indices, so the inner list is empty. The concatenated list therefore contains only the original string, and min correctly returns it unchanged.

If no adjacent pair satisfies both the ordering (s[i] < s[i-1]) and the even-sum condition, the comprehension again yields an empty list. The method again falls back to the original string as the sole candidate, ensuring a valid return value without additional branching.

The condition involving the bitwise & operator implicitly handles cases where the sum of the digit characters is odd. In those situations the expression evaluates to False, preventing the creation of a swap candidate for that index.

Performance Optimizations Observed

The implementation leverages Python’s native list comprehension syntax, which is executed in C-level loops, providing faster iteration compared with an explicit for loop written in pure Python. By constructing the candidate list in a single expression, the code avoids intermediate mutable structures and reduces the overhead of repeated method calls.

The use of the built-in min function is also a performance choice. min is implemented in C and performs a single pass over the supplied iterable, efficiently determining the smallest element without the need for manual comparison logic.

Finally, the slicing operations (s[:i-1], s[i+1:]) create new string objects only for the portions that change, while the unchanged prefix and suffix are shared with the original string where possible, minimizing unnecessary copying. This approach keeps the memory footprint modest for typical input sizes.

Imagine that the computer is looking at a line of toy blocks, and each block has a number painted on it. The goal is to make the group of numbers look as small as possible. The computer walks down the line of blocks and looks at two neighbors standing side by side. It asks if the two blocks have a special relationship where they can be swapped to make the whole line look smaller. Because the computer is very careful, it only tries to swap them if it finds a specific pattern that follows a hidden rule. It checks every pair of neighbors one by one, keeping the arrangement it likes best. Even though it looks at many different ways to arrange the blocks, it keeps the one that is the absolute smallest in the end.

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

Time: polynomial
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		Java	C++		Python		TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	Rust	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	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