# Reverse Only Letters
**Difficulty:** EASY
[External](https://leetcode.com/problems/reverse-only-letters)
Canonical: https://scaleengineer.com/dsa/problems/reverse-only-letters
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake), [Zoho](https://scaleengineer.com/companies/zoho), [Turing](https://scaleengineer.com/companies/turing)
---
## Problem
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"

**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 with ASCII values in the range `[33, 122]`.
* `s` does not contain `'\"'` or `'\\'`.

# Approaches
## Collect, Reverse, and Rebuild
This approach involves three main steps. First, we iterate through the input string to extract all the English letters and store them in a separate data structure, like a list or a `StringBuilder`. Second, we reverse this collection of letters. Finally, we build a new string by iterating through the original string one more time. If a character is a letter, we append the next letter from our reversed collection; otherwise, we append the non-letter character as is.
**Time:** O(N), where N is the length of the string. We perform two separate passes over the string, and reversing the list of letters takes time proportional to the number of letters (L). The total time is O(N) + O(L) + O(N), which simplifies to O(N) as L <= N. · **Space:** O(N), where N is the length of the string. We need extra space to store the collected letters, which can be up to N in the worst case. We also need space for the result `StringBuilder`, which is also O(N). Thus, the total auxiliary space is O(N).
**Pros:** Conceptually straightforward and easy to implement.; Separates the logic of finding letters and placing them, which can be easier to debug.
**Cons:** Requires extra space proportional to the number of letters in the string.; Requires two passes over the input string, which is less efficient than a single-pass solution.
### Explanation
The core idea is to separate the letters from the non-letters. We can make one pass through the string to collect all the letters into an auxiliary data structure. Once collected, we can easily reverse this collection. Then, we make a second pass through the original string to construct our final answer. When we encounter a position that originally held a letter, we take the next available letter from our reversed collection. When we encounter a non-letter, we place it back in its original position.

```java
class Solution {
    public String reverseOnlyLetters(String s) {
        StringBuilder letters = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) {
                letters.append(c);
            }
        }
        letters.reverse();
        
        StringBuilder result = new StringBuilder();
        int letterIndex = 0;
        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) {
                result.append(letters.charAt(letterIndex));
                letterIndex++;
            } else {
                result.append(c);
            }
        }
        
        return result.toString();
    }
}
```
### Algorithm
- Create a `StringBuilder` or a list to store only the letters from the input string `s`.
- Iterate through `s`. For each character, check if it's an English letter using `Character.isLetter()`.
- If it is a letter, append it to the `StringBuilder`/list.
- After the first pass, reverse the `StringBuilder`/list of letters.
- Create a new `StringBuilder` for the final result.
- Initialize a pointer/index for the reversed letters list to 0.
- Iterate through the original string `s` again. For each character:
- If the character is a letter, append the character from the reversed letters list at the current pointer, and increment the pointer.
- If the character is not a letter, append it directly to the result.
- Convert the result `StringBuilder` to a string and return it.

## Two-Pointer In-Place Swap
A more efficient approach uses two pointers, one starting from the beginning of the string (`left`) and the other from the end (`right`). The pointers move towards each other, skipping over any non-letter characters. When both pointers have found a letter, the characters at these two positions are swapped. This process continues until the pointers meet or cross, effectively reversing the letters in a single pass while leaving non-letter characters untouched.
**Time:** O(N), where N is the length of the string. Each pointer, `left` and `right`, traverses the array at most once. Therefore, the total number of operations is proportional to N. · **Space:** O(N). Although the swap is done 'in-place' on the character array, creating this array from the immutable input string requires O(N) space. This is still an improvement over the first approach which required O(N) for the letters list in addition to O(N) for the result.
**Pros:** More space-efficient as it avoids creating a separate list for letters.; Performs the reversal in a single pass over the string.
**Cons:** The logic of moving two pointers and swapping can be slightly more complex to grasp initially compared to the collect-and-rebuild method.
### Explanation
This method is a classic in-place reversal technique adapted for this specific problem. By converting the string to a character array, we can modify it directly. The `left` pointer seeks the first letter from the start, and the `right` pointer seeks the first letter from the end. Once found, they are swapped. This ensures that the first letter is swapped with the last, the second with the second-to-last, and so on, achieving the reversal. Non-letters are simply skipped over by the pointers, so they remain in their original positions.

```java
class Solution {
    public String reverseOnlyLetters(String s) {
        char[] chars = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right) {
            // Find the next letter from the left
            while (left < right && !Character.isLetter(chars[left])) {
                left++;
            }
            
            // Find the next letter from the right
            while (left < right && !Character.isLetter(chars[right])) {
                right--;
            }
            
            // Swap the letters
            if (left < right) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                
                // Move pointers
                left++;
                right--;
            }
        }
        
        return new String(chars);
    }
}
```
### Algorithm
- Convert the input string `s` into a character array `chars` to allow for in-place modification.
- Initialize two pointers: `left = 0` and `right = chars.length - 1`.
- Start a loop that continues as long as `left < right`.
- Inside the loop, move the `left` pointer forward until it points to a letter (`while (left < right && !Character.isLetter(chars[left])) { left++; }`).
- Similarly, move the `right` pointer backward until it points to a letter (`while (left < right && !Character.isLetter(chars[right])) { right--; }`).
- Once both pointers are at letters, swap the characters at `chars[left]` and `chars[right]`.
- After the swap, move both pointers towards the center: `left++` and `right--`.
- After the loop finishes, convert the modified character array `chars` back into a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String reverseOnlyLetters(String s) {
    char[] chars = s.toCharArray();
    int i = 0, j = s.length() - 1;
    while (i < j) {
      while (i < j && !Character.isLetter(chars[i])) {
        ++i;
      }
      while (i < j && !Character.isLetter(chars[j])) {
        --j;
      }
      if (i < j) {
        char t = chars[i];
        chars[i] = chars[j];
        chars[j] = t;
        ++i;
        --j;
      }
    }
    return new String(chars);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string reverseOnlyLetters(string s) {
    int i = 0, j = s.size() - 1;
    while (i < j) {
      while (i < j && !isalpha(s[i]))
        ++i;
      while (i < j && !isalpha(s[j]))
        --j;
      if (i < j) {
        swap(s[i], s[j]);
        ++i;
        --j;
      }
    }
    return s;
  }
};

```

### Python

```python
class Solution:
    def reverseOnlyLetters(self, s: str) -> str: s = list(s) i, j = 0, len(s) - 1 while i < j: while i < j and not s[i]. isalpha(): i += 1 while i < j and not s[j]. isalpha(): j -= 1 if i < j: s[i], s[j] = s[j], s[i] i, j = i + 1, j - 1 return '' . join(s)

```