algoadvance

Given a string s, return the string after reversing the letters of s without altering the positions of the non-letter characters.

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 of the following types:
  • English letters as well as punctuation marks (".”
  • Digits from 0 to 9.

Clarifying Questions

1. Should we consider uppercase and lowercase as distinct characters?
   • Yes, the problem does not require changing the case of the letters.
2. What should be done if the string consists of only non-letter characters?
   • The string should remain unchanged as there would be no letters to reverse.

Strategy

1. Two-pointer technique: Utilize two pointers, one starting from the beginning (left) and the other from the end (right) of the string.
2. Skip non-letter characters: Increment the left pointer until it finds a letter and decrement the right pointer until it finds a letter.
3. Swap letters: Swap the characters at the positions of left and right pointers and then move the pointers toward the center.
4. Join and return: Convert the list of characters back to a string and return it.

Time Complexity

• O(n) where n is the length of the string: Each character is processed at most once.

Code

def reverseOnlyLetters(s: str) -> str:
    # Convert string to list for mutable operations
    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:
            # Swap the letters
            s_list[left], s_list[right] = s_list[right], s_list[left]
            left += 1
            right -= 1
    
    return ''.join(s_list)

# Example usage
print(reverseOnlyLetters("ab-cd"))       # Output: "dc-ba"
print(reverseOnlyLetters("a-bC-dEf-ghIj")) # Output: "j-Ih-gfE-dCba"
print(reverseOnlyLetters("Test1ng-Leet=code-Q!")) # Output: "Qedo1ct-eeLg=ntse-T!"

In the above code:

• We convert the input string to a list to facilitate easy swapping of characters.
• We use a while loop with two pointers (left and right) to conditionally swap characters when they are both letters, otherwise, we adjust the pointers.
• Finally, we join the list back into a string and return it.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?