#917

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Reverse Only Letters

Reverse the characters of a string while skipping non-letter characters using a two-pointer technique.

Problem Statement

Given a string s, reverse the order of only the alphabetic characters while keeping all other characters (such as punctuation or digits) in their original positions. You must return the modified string.

For example, in the string "ab-cd", the reverse order of alphabetic characters would result in "dc-ba", while the dashes remain in place. You are required to implement an efficient solution with a time complexity of O(N) and a space complexity of O(N).

Examples

Example 1

Input: s = "ab-cd"

Output: "dc-ba"

Example details omitted.

Example 2

Input: s = "a-bC-dEf-ghIj"

Output: "j-Ih-gfE-dCba"

Example details omitted.

Example 3

Input: s = "Test1ng-Leet=code-Q!"

Output: "Qedo1ct-eeLg=ntse-T!"

Example details omitted.

Constraints

1 <= s.length <= 100
s consists of characters with ASCII values in the range [33, 122].
s does not contain '"' or ''.

Solution Approach

Two-Pointer Technique

Use a two-pointer approach to scan the string. One pointer starts at the beginning of the string, and the other starts at the end. Skip over non-letter characters and swap the letter characters until the pointers meet in the middle.

Efficient String Manipulation

By modifying the string in-place with two pointers, this approach avoids unnecessary space usage. The algorithm processes each character exactly once, ensuring optimal time complexity of O(N).

Handling Non-Alphabetic Characters

When the pointers encounter non-alphabetic characters, they simply skip them. This ensures that punctuation, numbers, and other symbols remain at their original positions while the alphabetic characters are reversed.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

The time complexity of O(N) is achieved because each character is visited at most once. The space complexity is O(N) due to the space used for storing the string, as we may need to modify it in-place with a new array or list.

What Interviewers Usually Probe

The candidate should clearly demonstrate an understanding of two-pointer techniques and its application to string manipulation.
Look for clarity in handling edge cases, such as strings with no alphabetic characters or strings where all characters are letters.
The candidate should be comfortable with explaining their thought process, particularly around skipping non-alphabetic characters while ensuring the overall time complexity is linear.

Common Pitfalls or Variants

Common pitfalls

Failing to handle edge cases like an empty string or a string with no alphabetic characters.
Not accounting for the fact that only letters need to be reversed, and other characters should remain in their original positions.
Overcomplicating the solution by using additional data structures when a simple in-place swap suffices.

Follow-up variants

Reverse a string while only skipping digits.
Modify the problem to handle uppercase and lowercase letters differently.
Add more non-alphabetic characters like symbols, ensuring they remain in place during the reversal.

FAQ

What is the best approach to solve the 'Reverse Only Letters' problem?

The two-pointer approach is ideal. It allows for efficient string manipulation by skipping non-letter characters while reversing only the alphabetic ones.

Why do we need to reverse only the letters in the string?

The problem specifies that we must reverse only the alphabetic characters while keeping all other characters, such as punctuation and digits, in their original positions.

How can I optimize my solution for the 'Reverse Only Letters' problem?

Using a two-pointer approach ensures an optimal time complexity of O(N) as it processes each character only once. No extra space is needed besides the string itself.

What are the edge cases I need to consider for 'Reverse Only Letters'?

Consider cases like an empty string, strings with no letters, or strings that are already reversed. Ensure that non-alphabetic characters are unaffected.

How does GhostInterview help with solving the 'Reverse Only Letters' problem?

GhostInterview guides you step-by-step through the problem, providing real-time feedback on common mistakes, offering hints, and ensuring your solution is both efficient and correct.

terminal

Solution

Solution 1: Two Pointers

We use two pointers $i$ and $j$ to point to the head and tail of the string respectively. When $i < j$, we continuously move $i$ and $j$ until $i$ points to an English letter and $j$ points to an English letter, then we swap $s[i]$ and $s[j]$. Finally, we return the string.

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Continue Practicing

#925 long pressed name #942 di string match #844 backspace string compare