Reverse Letters Then Special Characters in a String

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

You are given a string s that contains English letters and special characters. Your task is to reverse only the letters in the string while keeping all special characters in their original positions.

A letter is defined as an English alphabet character (a-z, A-Z). All other characters are considered special characters.

Return the resulting string after reversing the letters.

Examples

Example 1

Input: s = "ab-cd"
Output: "dc-ba"
Explanation: The letters 'a' and 'b' are swapped with 'd' and 'c', while '-' stays in place.

Example 2

Input: s = "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"
Explanation: All letters are reversed while '-' stays in place.

Example 3

Input: s = "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"
Explanation: Letters are reversed while '1', '-', '=', and '!' stay in place.

Constraints

1 <= s.length <= 100
s consists of English letters and special characters.

Table of Contents

• Examples
• Constraints
• Two Pointers Approach
• Extract and Reverse Approach
• Stack Approach

Two Pointers Approach

Intuition Use two pointers starting from both ends of the string. Move them towards each other, swapping letters when both pointers point to letters, and skipping special characters.

Steps

• Convert the string to a mutable character array.
• Initialize left pointer at 0 and right pointer at the end.
• While left < right:
  • If s[left] is not a letter, increment left.
  • If s[right] is not a letter, decrement right.
  • If both are letters, swap them and move both pointers.
• Convert the character array back to a string and return.

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 we consider the output as required space)
• Notes: This is the most space-efficient approach for in-place modification.

Extract and Reverse Approach

Intuition Extract all letters from the string, reverse them, and then place them back into the original positions where letters were located.

Steps

• Iterate through the string and collect all letters in a list.
• Reverse the list of letters.
• Iterate through the string again, replacing each letter position with the next letter from the reversed list.
• Return the resulting string.

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

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for storing the letters and the result
• Notes: This approach is straightforward but uses more space than the two pointers approach.

Stack Approach

Intuition Use a stack to store all letters in the string. Then iterate through the string again, popping letters from the stack to fill letter positions, which naturally reverses them.

Steps

• Push all letters from the string onto a stack.
• Create a result string by iterating through the original string.
• For each character, if it’s a letter, pop from the stack; otherwise, keep the original character.
• Return the result string.

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        stack = [c for c in s if c.isalpha()]
        
        result = []
        for c in s:
            if c.isalpha():
                result.append(stack.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 and result
• Notes: The stack naturally reverses the order of letters, making this approach intuitive.