We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reverse Only Letters

Difficulty: Easy

Problem Description

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.

Key Insights

  • We need to identify which characters in the string are letters and which are not.
  • We can utilize a two-pointer approach to efficiently reverse only the letters while keeping the non-letter characters in their original positions.
  • The algorithm should handle both uppercase and lowercase letters.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the string, since we traverse the string a constant number of times. Space Complexity: O(n) - for storing the characters in a list if we decide to use one for the output.

Solution

To solve this problem, we can use a two-pointer technique:

  1. Initialize two pointers, one at the beginning and one at the end of the string.
  2. Move the left pointer forward until we find a letter, and move the right pointer backward until we find a letter.
  3. Swap the letters at these two pointers and continue this process until the pointers meet.
  4. All non-letter characters remain untouched since we only swap letters.

Code Solutions

def reverseOnlyLetters(s: str) -> str:
    # Convert the string to a list for mutability
    s_list = list(s)
    left, right = 0, len(s_list) - 1
    
    while left < right:
        # Move the left pointer to the next letter
        while left < right and not s_list[left].isalpha():
            left += 1
        # Move the right pointer to the previous letter
        while left < right and not s_list[right].isalpha():
            right -= 1
        
        # Swap the letters
        if left < right:
            s_list[left], s_list[right] = s_list[right], s_list[left]
            left += 1
            right -= 1
            
    return ''.join(s_list)
← Back to All Questions