Abstract / Summary

Reverse the letters in a string while keeping all other characters in their original positions.

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 67% (300k+ submissions).

Typical patterns to solve this problem:

• String
• Two Pointers

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 Solution class with a single method reverseOnlyLetters. The method receives a string s and returns a new string where all alphabetic characters are reversed in order, while every non-alphabetic character remains in its original position. The algorithm works in two passes over the input: first it collects the letters, then it reconstructs the output by pulling letters from the end of that collection.

Key Steps

Collecting alphabetic characters

The first comprehension iterates over the input string and selects characters that satisfy the condition "a" <= c.lower() <= "z". This test treats both uppercase and lowercase letters uniformly by converting each character to lower case before the range check. The result is stored in the list letters.

letters = [c for c in s if "a" <= c.lower() <= "z"]

Rebuilding the result while preserving non-letters

A second loop walks through the original string again. For each character it decides whether to place a letter from the end of the letters list or to keep the original character unchanged. The decision uses the same alphabetic test as before. When a letter is needed, letters.pop() removes and returns the last element, which corresponds to the next character in the reversed order.

merged = []
for c in s:
    merged.append(letters.pop() if "a" <= c.lower() <= "z" else c)

Producing the final string

After the loop finishes, the list merged contains the characters of the desired output in correct sequence. The method joins the list into a single string and returns it.

return "".join(merged)

Edge Cases Handled

The algorithm naturally accommodates an empty input string. The list comprehension produces an empty letters list, the reconstruction loop does not execute any iterations, and the final join yields an empty string.

When the input consists solely of non-alphabetic symbols, the comprehension yields an empty letters list, and the reconstruction loop copies each original character unchanged, resulting in an output identical to the input.

If the string contains only letters, the letters list holds all characters, and each iteration of the reconstruction loop consumes one element via pop(). Because pop() removes from the end, the letters appear in reverse order in the final string.

Mixed-case letters are handled correctly because the test uses c.lower(). The original case of each letter is preserved because the actual character stored in letters is the original character, not its lower-cased version.

Strings with interleaved letters and symbols, such as "a-bC-dEf-ghIj", are processed by preserving the positions of the symbols (-, -, etc.) while reversing only the letters, exactly as required.

Performance Optimizations

The use of a list comprehension for the initial collection of letters creates the letters list in a single, efficient pass without intermediate data structures.

During reconstruction, the algorithm appends to a list merged rather than concatenating strings. List appends are amortized O(1) operations, avoiding the quadratic cost associated with repeated string concatenation in Python.

Retrieving letters with pop() from the end of the list is an O(1) operation, ensuring that each reversed character is accessed in constant time.

Finally, the conversion of the list of characters to a string with "".join(merged) is performed once, leveraging the highly optimized C implementation of join to produce the output efficiently.

Imagine there is a box filled with mixed things like shiny letters and dusty rocks. This code starts by picking out all the letters and putting them into a neat pile. After that, it looks at the box again from the very beginning. Whenever it finds a spot that used to have a letter, it takes the very last letter from that pile and places it into that spot. If it finds a dusty rock, it just leaves the rock exactly where it was. By the time it finishes, all the letters have swapped places to be backwards while everything else stays perfectly still in its original home.

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

Time: linear
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
	LeetcodeHelp	C++		Java			Python
	Progiez	C++		Java			Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	DimitrisJim							C
	everthis		JS
	fartem					Ruby
	fsq	C++
	JoshCrozier		JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007						Python
	lzl124631x	C++
	suxrobGM				C#
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
lzl124631x	C++
suxrobGM	C#
varunu28	Java

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