Reverse Only Letters

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

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

Return s after reversing it.

For example:

• s = "ab-cd" should return "dc-ba"
• s = "a-bC-dEf-ghIj" should return "j-Ih-gfE-dCba"
• s = "Test1ng-Leet=code-Q!" should return "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 '\\'.

def reverseOnlyLetters(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)

# Example Usage
s = "ab-cd"
print(reverseOnlyLetters(s)) # Output: dc-ba

s = "a-bC-dEf-ghIj"
print(reverseOnlyLetters(s)) # Output: j-Ih-gfE-dCba

s = "Test1ng-Leet=code-Q!"
print(reverseOnlyLetters(s)) # Output: Qedo1ct-eeLg=ntse-T!

Explanation:

1. Extract Letters: Create a list of all English letters (both lowercase and uppercase) from the input string s.
2. Reverse Letters: Reverse the extracted list of letters.
3. Rebuild String: Iterate through the original string s, and for each character:
   • If the character is an English letter, replace it with the next letter from the reversed list.
   • If the character is not an English letter, keep it in its original position.
4. Join and Return: Join the characters in the result list to form the final reversed string.

Big O Run-time Analysis:

• Time Complexity: O(N), where N is the length of the input string s. This is because we iterate through the string twice: once to extract the letters and once to rebuild the string.

Big O Space Usage Analysis:

• Space Complexity: O(N), where N is the length of the input string s. This is because we store the extracted letters in a separate list, which can grow up to the size of the input string if all characters are letters.

Edge Cases:

1. Empty String: If the input string is empty, the function should return an empty string.
2. String with No Letters: If the input string contains no letters, the function should return the original string.
3. String with Only Letters: If the input string contains only letters, the function should return the reversed string.
4. String with Special Characters Only: If the input string contains only special characters, the function should return the original string.