# Leetcode – Reverse Only Letters Solution in Python

Leetcode offers a plethora of problems that test a programmer’s ability to manipulate strings. Among these, the “Reverse Only Letters” problem is unique because it demands both string manipulation and character classification skills. This article will provide a detailed breakdown of the problem, the underlying logic, and Python-based solutions, followed by a complexity analysis.

1. Understanding the Problem Statement
2. Problem Analysis
3. Two-Pointer Technique
4. Python Implementation
5. Complexity Analysis
6. Alternate Approaches
7. Conclusion

## 1. Understanding the Problem Statement

### Problem:

Given a string S, return the “reversed” string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example:

Input: "ab-cd"
Output: "dc-ba"

## 2. Problem Analysis

At a first glance, it might seem like we just need to reverse the string. However, the challenge is to ensure that non-letter characters remain in their original positions. We need a strategy to skip these characters while performing the reversal.

## 3. Two-Pointer Technique

An intuitive way to approach this problem is by using the two-pointer technique. We can have two pointers:

• left: starts from the beginning of the string
• right: starts from the end of the string

While left is less than right, we can perform the following operations:

1. If the character at left is not a letter, increment left.
2. If the character at right is not a letter, decrement right.
3. If both characters are letters, swap them. Then, increment left and decrement right.

This approach ensures that we only reverse the positions of letter characters.

## 4. Python Implementation

Here’s a Python function implementing the two-pointer technique for this problem:

def reverseOnlyLetters(S: str) -> str:
S = list(S)  # Convert string to list for mutable operations
left, right = 0, len(S) - 1

while left < right:
# If character at left pointer is not a letter, move to next character
while left < right and not S[left].isalpha():
left += 1
# If character at right pointer is not a letter, move to previous character
while left < right and not S[right].isalpha():
right -= 1

# Swap the letters at left and right pointers
S[left], S[right] = S[right], S[left]
left, right = left + 1, right - 1

return ''.join(S)

## 5. Complexity Analysis

Time Complexity: O(n)
The algorithm iterates over the string with the two pointers, left and right. In the worst case, we go through the string once, leading to a linear time complexity.

Space Complexity: O(n)
We convert the input string to a list to easily swap characters. This conversion requires O(n) space.

## 6. Alternate Approaches

The two-pointer technique is efficient, but there might be other ways to tackle the problem:

1. Stack: Iterate through the string and push only the letters onto a stack. Then, iterate through the string again. If the character is a letter, pop from the stack and replace it. Else, move to the next character.
2. Regular Expressions: Using Python’s re module, one could extract all letters, reverse them, and then replace them back in the string.

## 7. Conclusion

The “Reverse Only Letters” problem is a classic example of how string manipulation can be combined with character classification in programming challenges. While the problem appears simple on the surface, it necessitates a clear understanding of string operations and character properties.