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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reverse Only Letters

Number: 953

Difficulty: Easy

Paid? No

Companies: Amazon, Google

Problem Description

Given a string s, reverse only the English letters in the string while keeping all non-letter characters in their original positions. For example, given s = "a-bC-dEf-ghIj", the output should be "j-Ih-gfE-dCba".

Key Insights

  • Use two pointers: one starting at the beginning and one at the end of the string.
  • Check if a character is an English letter.
  • If both pointers point to letters, swap them.
  • If one pointer points to a non-letter, move that pointer while keeping the non-letter character in place.
  • Continue until the pointers meet or cross.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, because each character is processed at most once. Space Complexity: O(n) to store the mutable copy of the string (or O(1) extra space if modifying in place in languages that allow it).

Solution

The solution employs a two-pointer technique. By initializing one pointer at the start and another at the end of the string, we scan inward. When both pointers point to letters, we swap the letters. If either pointer is on a non-letter character, we simply move that pointer without swapping. This ensures that non-letter characters remain in their original positions while the letters are reversed. A helper function can also be used to verify if a character is an English letter. The final result is constructed by converting the modified list of characters back into a string.

Code Solutions

# Convert the string to a list of characters for in-place modifications
def reverseOnlyLetters(s):
    # Convert string to list (mutable)
    s_list = list(s)
    left, right = 0, len(s_list) - 1
    
    # Helper function for checking if a character is a letter
    def is_letter(ch):
        return ch.isalpha()
    
    # Process until the two pointers meet
    while left < right:
        # If left pointer is not pointing to a letter, move rightward
        if not is_letter(s_list[left]):
            left += 1
        # If right pointer is not pointing to a letter, move leftward
        elif not is_letter(s_list[right]):
            right -= 1
        # Both are letters, swap and move pointers
        else:
            s_list[left], s_list[right] = s_list[right], s_list[left]
            left += 1
            right -= 1
            
    # Return the joined list back into a string
    return ''.join(s_list)

# Example usage
print(reverseOnlyLetters("a-bC-dEf-ghIj"))  # Output: "j-Ih-gfE-dCba"
← Back to All Questions