What is the time complexity of Reverse Only Letters?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Reverse Only Letters?

This problem uses Two Pointers, String. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Reverse Only Letters?

Insight 1: Recognize that only alphabetic characters need to be reversed, preserving the positions of non-alphabetic characters. Insight 2: Utilize a two-pointer approach for in-place reversal (in some language implementations) or a separate data structure to store letters and then rebuild the string.

Which companies ask LeetCode 917. Reverse Only Letters in interviews?

This problem is frequently asked at Snowflake, Turing, Zoho.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Reverse Only Letters - LeetCode 917 Solution

Q: How to solve Reverse Only Letters?

The Java, C, and C++ solutions use a two-pointer approach to reverse the letters in-place. The Python solution first extracts the letters into a separate list, reverses the list, and then rebuilds the string by iterating through the original string and replacing letters with the reversed letters, keeping other characters in their original positions. The core idea is to maintain two pointers, one at the beginning and one at the end of the string. Move the pointers inwards, skipping non-letter characters until both pointers point to letters. Then, swap the letters and continue the process until the pointers meet.

Reverse Only Letters - Complete Solution Guide

Reverse Only Letters is LeetCode problem 917, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 ASCI

Detailed Explanation

The problem asks us to reverse only the English letters within a given string while keeping all other characters (non-letters) in their original positions. The input is a string `s`, and the output should be a modified string where the letters are reversed. Constraints include the string length being between 1 and 100, characters having ASCII values between 33 and 122, and no quotation marks or backslashes.

Solution Approach

The Java, C, and C++ solutions use a two-pointer approach to reverse the letters in-place. The Python solution first extracts the letters into a separate list, reverses the list, and then rebuilds the string by iterating through the original string and replacing letters with the reversed letters, keeping other characters in their original positions. The core idea is to maintain two pointers, one at the beginning and one at the end of the string. Move the pointers inwards, skipping non-letter characters until both pointers point to letters. Then, swap the letters and continue the process until the pointers meet.

Step-by-Step Algorithm

Step 1: Initialize two pointers, `left` to 0 and `right` to `s.length() - 1`.
Step 2: While `left` is less than `right`:
Step 3: Move `left` to the right until `s[left]` is an alphabetic character or `left >= right`.
Step 4: Move `right` to the left until `s[right]` is an alphabetic character or `left >= right`.
Step 5: If `left` is still less than `right`, swap `s[left]` and `s[right]`, increment `left`, and decrement `right`.
Step 6: After the loop finishes, return the modified string.

Key Insights

Insight 1: Recognize that only alphabetic characters need to be reversed, preserving the positions of non-alphabetic characters.
Insight 2: Utilize a two-pointer approach for in-place reversal (in some language implementations) or a separate data structure to store letters and then rebuild the string.
Insight 3: The `isalpha()` function is crucial for efficiently identifying alphabetic characters.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Two Pointers, String.

Companies

Asked at: Snowflake, Turing, Zoho.

Reverse Only Letters | LeetCode 917

Easy

Two Pointers String

Time: O(n)Space: O(n)

Solution Code

Available in:

class Solution {
    public String reverseOnlyLetters(String s) {
        char[] chars = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetter(chars[left])) {
                left++;
            }
            while (left < right && !Character.isLetter(chars[right])) {
                right--;
            }
            if (left < right) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }
        return new String(chars);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 917: Reverse Only Letters - Detailed explanation and solution approaches.

Topics

Two Pointers String

Companies

SnowflakeTuringZoho

Stats

Difficulty:Easy

Languages:4

Companies:3

Problem #:917

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize two pointers, `left` to 0 and `right` to `s.length() - 1`.
2
Step 2: While `left` is less than `right`:
3
Step 3: Move `left` to the right until `s[left]` is an alphabetic character or `left >= right`.
4
Step 4: Move `right` to the left until `s[right]` is an alphabetic character or `left >= right`.
5
Step 5: If `left` is still less than `right`, swap `s[left]` and `s[right]`, increment `left`, and decrement `right`.
6
Step 6: After the loop finishes, return the modified string.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is linear because each character in the string is visited at most a constant number of times. The space complexity for the in-place solutions is constant because it uses a fixed amount of extra space regardless of the input size (only a few variables like `left`, `right`, and `temp`). Python's usage of the `letters` list creates a dependency on the input size, resulting in O(n) space.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a Stack

Iterate through the string, pushing letters onto a stack. Then, iterate through the string again, replacing letters with the top element from the stack and keeping non-letters as they are.

Time: O(n)Space: O(n)

Trade-offs: This approach is easier to understand for some but requires O(n) extra space for the stack, even when compared to Python's implementation.

✨

Key Insights

1Insight 1: Recognize that only alphabetic characters need to be reversed, preserving the positions of non-alphabetic characters.
2Insight 2: Utilize a two-pointer approach for in-place reversal (in some language implementations) or a separate data structure to store letters and then rebuild the string.
3Insight 3: The `isalpha()` function is crucial for efficiently identifying alphabetic characters.

📚

Key Terms Explained

For Students

Two Pointers

Using two indices to traverse data from different positions simultaneously.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string. The algorithm handles an empty string correctly as the `while` loop condition `left < right` will be false from the beginning, and the original string is returned.
Edge case 2: String with no letters. The `while` loops will advance `left` and decrement `right` until `left >= right` without any swaps, resulting in the original string being returned.
Edge case 3: String with only letters. The algorithm will correctly reverse the entire string.
Edge case 4: String with consecutive non-letter characters. The inner `while` loops will skip these efficiently.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not checking if `left < right` before swapping. This can lead to incorrect behavior and out-of-bounds access if the pointers cross each other.

✗Common mistake 2: Not properly handling non-letter characters. Failing to skip non-letter characters will cause the letters to be swapped with non-letters, resulting in an incorrect output.

✗Common mistake 3: Assuming the input string contains only ASCII characters within the given range. Incorrectly handling other character sets could lead to issues.

✗Common mistake 4: In C, forgetting to null-terminate the returned string if modifications were made that shorten the original string or using the same memory address for the same string.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data cleaning and preprocessing. In many data-related tasks, strings need to be cleaned or modified before analysis. This algorithm can be used to reverse specific parts of a string while preserving others.

🏦Real-world scenario 2: Password masking or obfuscation. Certain parts of a password or sensitive information might need to be reversed or manipulated for security reasons while keeping other parts intact.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The two-pointer technique is powerful for sorted arrays. The key insight is recognizing when elements can be processed from both ends simultaneously.

🎯 Interview Tip

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ Watch Out

The most common mistake is not handling the case when pointers meet. Always consider the termination condition.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 18, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 30

❓

Frequently Asked Questions

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Reverse Only Letters"?

For this easy-level Two Pointers problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?