Reverse Only Letters

Difficulty: Easy | Acceptance: 68.40% | Paid: No Topics: Two Pointers, String

Given a string s, reverse the string according to the following rules:

All the characters that are not English letters remain in the same position. All the English letters (lowercase or uppercase) should be reversed.

Return s after reversing it.

• Examples
• Constraints
• Two Pointers Approach
• Stack Approach
• String Builder Approach

Examples

Example 1:

Input: s = "ab-cd"
Output: "dc-ba"

Example 2:

Input: s = "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: s = "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Constraints

1 <= s.length <= 100
s consists of characters with ASCII values in the range [33, 122].
s does not contain '\"' or '\\'.

Two Pointers Approach

Intuition Use two pointers starting from both ends of the string, moving towards each other while swapping only the letters.

Steps

• Initialize left pointer at 0 and right pointer at the end of the string
• Convert string to a mutable character array
• While left < right, skip non-letter characters by moving pointers
• When both pointers point to letters, swap them and move both pointers
• Return the joined character array as a string

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        s_list = list(s)
        left, right = 0, len(s) - 1
        
        while left < right:
            if not s_list[left].isalpha():
                left += 1
            elif not s_list[right].isalpha():
                right -= 1
            else:
                s_list[left], s_list[right] = s_list[right], s_list[left]
                left += 1
                right -= 1
        
        return ''.join(s_list)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the character array (or O(1) if using in-place modification in languages that support it)
• Notes: Most space-efficient approach with optimal time complexity

Stack Approach

Intuition Collect all letters in a stack, then iterate through the string replacing each letter with the top of the stack (which gives reversed order).

Steps

• Iterate through the string and push all letters onto a stack
• Iterate through the string again, building the result
• For each character, if it’s a letter, pop from the stack; otherwise, keep the original character
• Return the constructed result string

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        letters = [c for c in s if c.isalpha()]
        result = []
        
        for c in s:
            if c.isalpha():
                result.append(letters.pop())
            else:
                result.append(c)
        
        return ''.join(result)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the stack to store all letters
• Notes: Intuitive approach but uses extra space for the stack

String Builder Approach

Intuition Convert the string to a mutable character array and use two pointers with inner while loops to skip non-letter characters before swapping.

Steps

• Convert string to a character array/list
• Initialize left and right pointers
• Use inner while loops to advance pointers past non-letter characters
• Swap letters when both pointers are valid
• Continue until pointers meet or cross

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        s_list = list(s)
        left, right = 0, len(s) - 1
        
        while left < right:
            while left < right and not s_list[left].isalpha():
                left += 1
            while left < right and not s_list[right].isalpha():
                right -= 1
            
            if left < right:
                s_list[left], s_list[right] = s_list[right], s_list[left]
                left += 1
                right -= 1
        
        return ''.join(s_list)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the character array
• Notes: Similar to two pointers but with cleaner inner loop structure for skipping non-letters