Domain 1EasyCORE

Reverse Only Letters

The problem requires reversing only the letters in a given string `S`, while keeping all non-letter characters (such as punctuation and spaces) in their original positions. The input is a string `S` with a length constraint of up to 100 characters, and each character has an ASCII code between 33 and 122.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

917. Reverse Only Letters

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 59.4%


Problem Breakdown

The problem requires reversing only the letters in a given string S, while keeping all non-letter characters (such as punctuation and spaces) in their original positions. The input is a string S with a length constraint of up to 100 characters, and each character has an ASCII code between 33 and 122.

Inputs:

  • A single string S.

Outputs:

  • A string where all letters are reversed in order, but non-letter characters remain in their original positions.

Implicit Constraints or Edge Cases:

  • The string can be empty.
  • The string may contain only non-letter characters.
  • The string may contain a mix of uppercase and lowercase letters.

Intuition

A brute-force approach would involve iterating through the string twice: once to collect all the letters, and another time to construct the result by placing the collected letters back in reverse order while keeping non-letter characters in their original positions. This approach is inefficient because it requires two passes over the string and additional space to store the letters.

A better approach involves using a two-pointer technique. We can initialize two pointers: one at the beginning (left) and one at the end (right) of the string. We then move these pointers towards each other, swapping letters when both pointers point to letters, and skipping non-letter characters by moving the respective pointer forward or backward.

Approach

  1. Initialize two pointers, left at the start of the string and right at the end.
  2. While left is less than right, do the following:
    • If both S[left] and S[right] are letters, swap them and move both pointers inward.
    • If S[left] is not a letter, increment left.
    • If S[right] is not a letter, decrement right.
  3. Continue this process until the two pointers meet or cross each other.
  4. Return the modified string.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. Each character is processed at most once.
  • Space Complexity: O(1) if we consider the input and output as part of the space complexity, otherwise O(n) due to the creation of a list for the result.

Solution

def reverseOnlyLetters(S: str) -> str:
    S = list(S)  # Convert string to list for easy swapping
    left, right = 0, len(S) - 1
    
    while left < right:
        if S[left].isalpha() and S[right].isalpha():
            S[left], S[right] = S[right], S[left]
            left += 1
            right -= 1
        elif not S[left].isalpha():
            left += 1
        elif not S[right].isalpha():
            right -= 1
    
    return ''.join(S)

Edge Cases Handled

  • Empty String: The function will correctly return an empty string if the input is empty.
  • String with No Letters: If the string contains no letters, it will be returned unchanged.
  • String with Mixed Characters: The function handles strings with a mix of uppercase and lowercase letters, as well as non-letter characters.