> For the complete documentation index, see [llms.txt](https://programming.arora-aditya.com/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://programming.arora-aditya.com/leetcode/unsorted/917.-reverse-only-letters.md).

# 917. Reverse Only Letters

## Approach 1: Front and Back switching

```python
class Solution:
    def reverseOnlyLetters(self, S):
        """
        https://leetcode.com/problems/reverse-only-letters/description/
        :type S: str
        :rtype: str
        """
        if S == "":
            return ""
        S = list(S)
        i, j = 0, len(S) - 1
        while i < j:
            if S[i].isalpha() == False:
                i += 1
            if S[j].isalpha() == False:
                j -= 1
            else:
                S[i], S[j] = S[j], S[i]
                i += 1
                j -= 1
        return ''.join(S)

```

This approach required keeping track of two positions in the array where we stay until we can find valid characters, once we find two characters at the front and back, we will switch them.

> **Time Complexity:** *O(1), just indices*
>
> **Space Complexity:** *O(n)*

## Approach 2: Minor improvements to Approach 1

Instead of increasing `i` and `j` one by one, it can be optimized by using nesting `while` loops to increment/decrement until the next character on both ends and swap when we find them

```python
class Solution:
    def reverseOnlyLetters(self, S):
        """
        https://leetcode.com/problems/reverse-only-letters/description/
        :type S: str
        :rtype: str
        """
        if S == "": return ""
        le = len(S)
        S = list(S)
        i, j = 0, le - 1
        while i < j:
            while i < j and S[i].isalpha() == False:
                i += 1
            while j > i and S[j].isalpha() == False:
                j -= 1
            if i < j:
                S[i], S[j] = S[j], S[i]
                i += 1
                j -= 1
        return ''.join(S)
```

The runtime and space complexity remains the same

> **Time Complexity:** *O(1), just indices*
>
> **Space Complexity:** *O(n)*