# LeetCode 917: Reverse Only Letters

## Problem Restatement

We are given a string `s`.

Reverse only the English letters in the string.

All characters that are not English letters must stay at the same index. Both lowercase and uppercase English letters are reversed together.

For example:

```python
s = "ab-cd"
```

The letters are:

```python
a, b, c, d
```

After reversing the letters:

```python
d, c, b, a
```

The hyphen stays in the same position.

Output:

```python
"dc-ba"
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` |
| Output | String after reversing only English letters |
| Fixed characters | Digits, punctuation, and symbols stay in place |
| Reversed characters | Lowercase and uppercase English letters |

Function shape:

```python
def reverseOnlyLetters(s: str) -> str:
    ...
```

## Examples

Example 1:

```python
s = "ab-cd"
```

Output:

```python
"dc-ba"
```

Example 2:

```python
s = "a-bC-dEf-ghIj"
```

Output:

```python
"j-Ih-gfE-dCba"
```

Example 3:

```python
s = "Test1ng-Leet=code-Q!"
```

Output:

```python
"Qedo1ct-eeLg=ntse-T!"
```

## First Thought: Extract Letters, Then Put Them Back

One simple approach is:

1. Collect all letters from the string.
2. Reverse that letter list.
3. Build a new string:
   - If the original character is a letter, take the next reversed letter.
   - Otherwise, keep the original character.

```python
class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        letters = [ch for ch in s if ch.isalpha()]
        letters.reverse()

        result = []
        index = 0

        for ch in s:
            if ch.isalpha():
                result.append(letters[index])
                index += 1
            else:
                result.append(ch)

        return "".join(result)
```

This works and is easy to reason about.

But we can solve it with two pointers and direct swaps.

## Key Insight

This is a normal reverse operation with a filter.

In a normal string reversal, we swap the first character with the last, the second with the second-last, and so on.

Here, only letters participate in the reversal.

So we use two pointers:

| Pointer | Role |
|---|---|
| `left` | Finds the next letter from the front |
| `right` | Finds the next letter from the back |

When both pointers are at letters, swap them.

When a pointer is at a non-letter, skip it.

Because we never swap non-letter characters, they remain fixed.

## Algorithm

1. Convert the string into a list of characters.
2. Set `left = 0`.
3. Set `right = len(s) - 1`.
4. While `left < right`:
   - Move `left` rightward until it points to a letter.
   - Move `right` leftward until it points to a letter.
   - Swap the two letters.
   - Move both pointers inward.
5. Join the list and return the result.

## Correctness

The algorithm swaps letters from the outside inward.

The left pointer always finds the next unreversed letter from the front.

The right pointer always finds the next unreversed letter from the back.

When these two letters are swapped, they move to their correct reversed positions among the letters.

Non-letter characters are only skipped. They are never moved or overwritten, so they stay at their original indices.

The process continues until the pointers meet or cross. At that point, every letter has been paired with its corresponding letter from the opposite side, and every non-letter remains fixed.

Therefore, the returned string has all English letters reversed and all non-letter characters unchanged.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each pointer scans across the string once |
| Space | `O(n)` | Python strings are immutable, so we use a character list |

## Implementation

```python
class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        chars = list(s)

        left = 0
        right = len(chars) - 1

        while left < right:
            while left < right and not chars[left].isalpha():
                left += 1

            while left < right and not chars[right].isalpha():
                right -= 1

            chars[left], chars[right] = chars[right], chars[left]

            left += 1
            right -= 1

        return "".join(chars)
```

## Code Explanation

Convert the string into a mutable list:

```python
chars = list(s)
```

Start two pointers at both ends:

```python
left = 0
right = len(chars) - 1
```

Skip non-letters on the left:

```python
while left < right and not chars[left].isalpha():
    left += 1
```

Skip non-letters on the right:

```python
while left < right and not chars[right].isalpha():
    right -= 1
```

Now both sides point to letters, so we swap them:

```python
chars[left], chars[right] = chars[right], chars[left]
```

Then move inward:

```python
left += 1
right -= 1
```

Finally, rebuild the string:

```python
return "".join(chars)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.reverseOnlyLetters("ab-cd") == "dc-ba"
    assert s.reverseOnlyLetters("a-bC-dEf-ghIj") == "j-Ih-gfE-dCba"
    assert s.reverseOnlyLetters("Test1ng-Leet=code-Q!") == "Qedo1ct-eeLg=ntse-T!"
    assert s.reverseOnlyLetters("7_28]") == "7_28]"
    assert s.reverseOnlyLetters("a") == "a"
    assert s.reverseOnlyLetters("A-b") == "b-A"
    assert s.reverseOnlyLetters("z<*zj") == "j<*zz"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"ab-cd"` | Basic fixed hyphen case |
| `"a-bC-dEf-ghIj"` | Mixed uppercase, lowercase, and symbols |
| `"Test1ng-Leet=code-Q!"` | Main complex sample |
| `"7_28]"` | No letters |
| `"a"` | Single letter |
| `"A-b"` | Case is preserved as characters move |
| `"z<*zj"` | Multiple fixed symbols between letters |