Logo

Kode$word

Reverse Only Letters – Two Pointer Strategy Explained (LeetCode 917)
Reverse Only Letters – Two Pointer Strategy Explained (LeetCode 917)

Reverse Only Letters – Two Pointer Strategy Explained (LeetCode 917)

Reversing Letters While Preserving Special Characters in Place

19 views
0
0
Two PointersString ManipulationLeetCodeEasy
Github icon

🔗 Problem Link

LeetCode 917 – Reverse Only Letters

👉 https://leetcode.com/problems/reverse-only-letters/

Introduction

This is a very clean two-pointer problem.

The challenge is not just reversing a string —

it’s reversing only the letters while keeping all non-letter characters in their original positions.

This problem strengthens:

  1. Two pointer technique
  2. Character validation logic
  3. In-place string manipulation

Let’s break it down.

📌 Problem Understanding

You are given a string s.

Rules:

  1. All non-English letters must remain at the same index.
  2. Only English letters (uppercase or lowercase) should be reversed.

Return the modified string.

Example 1

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

Only letters are reversed.

Hyphen stays at same position.

Example 2

Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3

Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Notice:

  1. Numbers, -, =, ! stay fixed.
  2. Only letters move.

🧠 Intuition

The first thought might be:

  1. Extract all letters
  2. Reverse them
  3. Put them back

But that would require extra space.

Instead, we can solve this efficiently using Two Pointers.

🚀 Two Pointer Approach

We use:

  1. i → starting from left
  2. j → starting from right

Steps:

  1. Convert string into char array.
  2. Move i forward until it points to a letter.
  3. Move j backward until it points to a letter.
  4. Swap letters.
  5. Continue until i < j.

💻 Your Code

class Solution {
public String reverseOnlyLetters(String s) {
int i = 0;
int j = s.length() - 1;
char arr[] = s.toCharArray();

while(i < j){
boolean l = ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') ||
('a' <= s.charAt(i) && s.charAt(i) <= 'z');

boolean r = ('A' <= s.charAt(j) && s.charAt(j) <= 'Z') ||
('a' <= s.charAt(j) && s.charAt(j) <= 'z');

if(l && r){
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}else if(l){
j--;
}else if(r){
i++;
}else{
i++;
j--;
}
}
return new String(arr);
}
}

🔍 Step-by-Step Explanation

1️⃣ Convert to Character Array

char arr[] = s.toCharArray();

Strings are immutable in Java.

So we convert to char array to modify it.

2️⃣ Initialize Two Pointers

int i = 0;
int j = s.length() - 1;

We start from both ends.

3️⃣ Check If Characters Are Letters

boolean l = ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') ||
('a' <= s.charAt(i) && s.charAt(i) <= 'z');

You manually check ASCII ranges for uppercase and lowercase letters.

Same logic for r.

4️⃣ Swap When Both Are Letters

if(l && r){
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}

Only swap letters.

5️⃣ Move Pointers When One Is Not Letter

  1. If left is letter but right is not → move j
  2. If right is letter but left is not → move i
  3. If both are not letters → move both

This ensures:

Non-letter characters remain in their positions.

🎯 Why This Works

We never move non-letter characters.

We only swap valid letters.

Since we use two pointers:

  1. Time complexity stays linear.
  2. No extra array needed for letters.

⏱ Complexity Analysis

Time Complexity: O(n)

Each character is visited at most once.

Space Complexity: O(n)

Because we convert string to char array.

(If considering output string creation, still O(n))

🔥 Cleaner Optimization

Instead of manually checking ASCII ranges, Java provides:

Character.isLetter(c)

Cleaner version:

class Solution {
public String reverseOnlyLetters(String s) {
int i = 0, j = s.length() - 1;
char[] arr = s.toCharArray();

while(i < j){
if(!Character.isLetter(arr[i])){
i++;
}else if(!Character.isLetter(arr[j])){
j--;
}else{
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}

return new String(arr);
}
}

Much cleaner and readable.

🏁 Final Thoughts

This problem teaches:

  1. Two pointer pattern
  2. In-place string reversal
  3. Character validation logic
  4. Clean pointer movement strategy

It’s a simple but powerful pattern that appears often in interviews.

If you master this, you can easily solve:

  1. Reverse Vowels of a String
  2. Valid Palindrome
  3. Reverse String II
  4. Palindrome with One Removal


Related Articles

Reverse Vowels of a String – From Extra Space Approach to Two Pointer Optimization (LeetCode 345)

Reverse Vowels of a String – From Extra Space Approach to Two Pointer Optimization (LeetCode 345)

Understanding Different Ways to Reverse Only Vowels Efficiently

Read Article
Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained

Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained

Understand how to convert a binary string into an alternating pattern with the minimum number of flips using a simple greedy approach.

Read Article
Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

Using HashMap and Array Optimization to Detect Anagrams Efficiently

Read Article
Find the Difference – Smart ASCII Sum Trick (LeetCode 389)

Find the Difference – Smart ASCII Sum Trick (LeetCode 389)

Solving the Problem Using Character Arithmetic Instead of Extra Space

Read Article

Ai Assistant Kas