LeetCode 917: Reverse Only Letters

Problem Restatement

We are given a string s.

Reverse only the English letters in the string.

All characters that are not English letters must stay at the same index. Both lowercase and uppercase English letters are reversed together.

For example:

s = "ab-cd"

The letters are:

a, b, c, d

After reversing the letters:

d, c, b, a

The hyphen stays in the same position.

Output:

"dc-ba"

Input and Output

Function shape:

def reverseOnlyLetters(s: str) -> str:
    ...

Examples

Example 1:

s = "ab-cd"

Output:

"dc-ba"

Example 2:

s = "a-bC-dEf-ghIj"

Output:

"j-Ih-gfE-dCba"

Example 3:

s = "Test1ng-Leet=code-Q!"

Output:

"Qedo1ct-eeLg=ntse-T!"

First Thought: Extract Letters, Then Put Them Back

One simple approach is:

1. Collect all letters from the string.
2. Reverse that letter list.
3. Build a new string:
   • If the original character is a letter, take the next reversed letter.
   • Otherwise, keep the original character.

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        letters = [ch for ch in s if ch.isalpha()]
        letters.reverse()

        result = []
        index = 0

        for ch in s:
            if ch.isalpha():
                result.append(letters[index])
                index += 1
            else:
                result.append(ch)

        return "".join(result)

This works and is easy to reason about.

But we can solve it with two pointers and direct swaps.

Key Insight

This is a normal reverse operation with a filter.

In a normal string reversal, we swap the first character with the last, the second with the second-last, and so on.

Here, only letters participate in the reversal.

So we use two pointers:

When both pointers are at letters, swap them.

When a pointer is at a non-letter, skip it.

Because we never swap non-letter characters, they remain fixed.

Algorithm

1. Convert the string into a list of characters.
2. Set left = 0.
3. Set right = len(s) - 1.
4. While left < right:
   • Move left rightward until it points to a letter.
   • Move right leftward until it points to a letter.
   • Swap the two letters.
   • Move both pointers inward.
5. Join the list and return the result.

Correctness

The algorithm swaps letters from the outside inward.

The left pointer always finds the next unreversed letter from the front.

The right pointer always finds the next unreversed letter from the back.

When these two letters are swapped, they move to their correct reversed positions among the letters.

Non-letter characters are only skipped. They are never moved or overwritten, so they stay at their original indices.

The process continues until the pointers meet or cross. At that point, every letter has been paired with its corresponding letter from the opposite side, and every non-letter remains fixed.

Therefore, the returned string has all English letters reversed and all non-letter characters unchanged.

Complexity

Implementation

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        chars = list(s)

        left = 0
        right = len(chars) - 1

        while left < right:
            while left < right and not chars[left].isalpha():
                left += 1

            while left < right and not chars[right].isalpha():
                right -= 1

            chars[left], chars[right] = chars[right], chars[left]

            left += 1
            right -= 1

        return "".join(chars)

Code Explanation

Convert the string into a mutable list:

chars = list(s)

Start two pointers at both ends:

left = 0
right = len(chars) - 1

Skip non-letters on the left:

while left < right and not chars[left].isalpha():
    left += 1

Skip non-letters on the right:

while left < right and not chars[right].isalpha():
    right -= 1

Now both sides point to letters, so we swap them:

chars[left], chars[right] = chars[right], chars[left]

Then move inward:

left += 1
right -= 1

Finally, rebuild the string:

return "".join(chars)

Testing

def run_tests():
    s = Solution()

    assert s.reverseOnlyLetters("ab-cd") == "dc-ba"
    assert s.reverseOnlyLetters("a-bC-dEf-ghIj") == "j-Ih-gfE-dCba"
    assert s.reverseOnlyLetters("Test1ng-Leet=code-Q!") == "Qedo1ct-eeLg=ntse-T!"
    assert s.reverseOnlyLetters("7_28]") == "7_28]"
    assert s.reverseOnlyLetters("a") == "a"
    assert s.reverseOnlyLetters("A-b") == "b-A"
    assert s.reverseOnlyLetters("z<*zj") == "j<*zz"

    print("all tests passed")

run_tests()

Test meaning: