Leetcode – Reverse Only Letters Solution in Python

Spread the love

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.

Table of Contents:

  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.

Leave a Reply