Reverse Only Letters

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.

Example 1:
Input: s = "ab-cd"
Output: "dc-ba"
Explanation: Letters are [a,b,c,d], reversed = [d,c,b,a]. Non-letter '-' stays in position 2.

Example 2:
Input: s = "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"
Explanation: Letters are [a,b,C,d,E,f,g,h,I,j], reversed = [j,I,h,g,f,E,d,C,b,a]. Non-letters stay in their positions.

Example 3:
Input: s = "Test1ng-Leet=code-Q!"
Output: "Qedo1teleocl-tseT=gnit-s!"

Constraints

1 <= s.length <= 100
s consists of characters with ASCII values in the range [33, 122]
s does not contain '\"' or '\\'

Signature

def solution(s: str) -> str: ...

Complexity

Time: O(n)
Space: O(n)

Hints

Pattern: Two pointers with character filtering
Approach: Use left and right pointers. Skip non-letters at each pointer. When both point to letters, swap them and move inward.
Complexity: Skip non-letter characters while swapping letters from both ends

Solutions

Python

def solution(s):
    results = list(s)

    i, j = 0, len(results) - 1

    while i < j:
        a_alpha = results[i].isalpha()
        b_alpha = results[j].isalpha()
        if a_alpha and b_alpha:
            results[i], results[j] = results[j], results[i]
            i += 1
            j -= 1
        elif not a_alpha:
            i += 1
        elif not b_alpha:
            j -= 1

    return "".join(results)