Valid Palindrome Two Pointer in DSA Java

Mental Model

Check if a word reads the same forwards and backwards by comparing letters from both ends moving towards the center.

Analogy: Imagine two friends starting at opposite ends of a line of people, checking if each pair of friends look the same until they meet in the middle.

h -> e -> l -> l -> o
↑                 ↑
left             right

Dry Run Walkthrough

Input: string: "racecar"

Goal: Determine if the string reads the same forwards and backwards ignoring case and non-letter characters.

Step 1: Initialize two pointers: left at start (r), right at end (r)

r -> a -> c -> e -> c -> a -> r
↑                             ↑

Why: We start comparing characters from both ends.

Step 2: Compare characters at left and right: 'r' == 'r', move both pointers inward

r -> a -> c -> e -> c -> a -> r
    ↑                     ↑

Why: Matching characters mean we continue checking inside.

Step 3: Compare characters at left and right: 'a' == 'a', move both pointers inward

r -> a -> c -> e -> c -> a -> r
        ↑               ↑

Why: Still matching, continue moving inward.

Step 4: Compare characters at left and right: 'c' == 'c', move both pointers inward

r -> a -> c -> e -> c -> a -> r
            ↑         ↑

Why: Characters match, move pointers closer.

Step 5: Left and right pointers meet at 'e', single middle character means palindrome

r -> a -> c -> e -> c -> a -> r
              ↑

Why: Middle reached, all pairs matched.

Result:

r -> a -> c -> e -> c -> a -> r
Palindrome: true

Annotated Code

DSA Java

public class ValidPalindrome {
    public static boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            // Skip non-alphanumeric from left
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            // Skip non-alphanumeric from right
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            // Compare characters ignoring case
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String input = "racecar";
        boolean result = isPalindrome(input);
        System.out.println(input + " -> Palindrome: " + result);
    }
}

while (left < right) {

loop until pointers meet or cross

while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { left++; }

skip non-letter characters from left

while (left < right && !Character.isLetterOrDigit(s.charAt(right))) { right--; }

skip non-letter characters from right

if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) { return false; }

compare characters ignoring case, return false if mismatch

left++; right--;

move pointers inward to check next pair

Output

racecar -> Palindrome: true

Complexity Analysis

Time: O(n) because we scan the string once with two pointers moving inward

Space: O(1) because we use only fixed extra space for pointers and comparisons

vs Alternative: Compared to reversing the string and comparing, this method uses less space and stops early on mismatch

Edge Cases

empty string

returns true because empty string reads the same forwards and backwards

DSA Java

while (left < right)

string with only non-alphanumeric characters

skips all characters and returns true

DSA Java

while (left < right && !Character.isLetterOrDigit(s.charAt(left)))

string with mixed case and punctuation, e.g. "A man, a plan, a canal: Panama"

ignores punctuation and case, returns true

DSA Java

if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))

When to Use This Pattern

When you need to check if a string reads the same forwards and backwards ignoring spaces or punctuation, use the two pointer pattern to compare characters from both ends efficiently.

Common Mistakes

Mistake: Not skipping non-alphanumeric characters before comparing
Fix: Add loops to move pointers past non-letter/digit characters before comparison

Mistake: Comparing characters without ignoring case
Fix: Convert characters to lowercase before comparing

Summary

Checks if a string is a palindrome by comparing characters from both ends moving inward.

Use when you want to verify palindrome ignoring spaces, punctuation, and case efficiently.

The key insight is to use two pointers moving inward and skip unwanted characters before comparing.

Practice

1. What is the main idea behind the two-pointer technique to check if a string is a palindrome?

easy

A. Sort the characters and check if the sorted string equals the original

B. Use two pointers starting from both ends and move towards the center comparing characters

C. Count the frequency of each character and check if all are even

D. Reverse the string and compare it with the original string

Solution

1. Step 1: Understand the two-pointer approach

   Two pointers start at the beginning and end of the string and move inward.

2. Step 2: Compare characters at pointers

   If characters at both pointers match, move pointers closer; if not, string is not palindrome.

3. Final Answer:

   Use two pointers starting from both ends and move towards the center comparing characters -> Option B

4. Quick Check:

   Two-pointer technique = Compare ends inward [OK]

Hint: Compare characters from both ends moving inward [OK]

Common Mistakes:

• Trying to reverse the string instead of using pointers
• Checking only half the string without comparing both ends
• Ignoring case or non-alphanumeric characters

2. Which of the following Java code snippets correctly initializes two pointers for palindrome checking on string s?

easy

A. int left = 0, right = s.length() - 1;

B. int left = 0, right = s.length();

C. int left = 1, right = s.length() - 1;

D. int left = 0, right = s.length() + 1;

Solution

1. Step 1: Identify valid pointer initialization

   String indices start at 0 and end at length - 1, so right pointer must be s.length() - 1.

2. Step 2: Check each option

   int left = 0, right = s.length() - 1; correctly sets left to 0 and right to s.length() - 1; others are off by one or invalid.

3. Final Answer:

   int left = 0, right = s.length() - 1; -> Option A

4. Quick Check:

   Right pointer = last index = length - 1 [OK]

Hint: Right pointer = string length minus one [OK]

Common Mistakes:

• Setting right pointer to s.length() causing out-of-bounds
• Starting left pointer at 1 instead of 0
• Using length + 1 causing errors

3. What will be the output of the following Java code snippet?

String s = "A man, a plan, a canal: Panama";
boolean isPalindrome = true;
int left = 0, right = s.length() - 1;
while (left < right) {
  char leftChar = Character.toLowerCase(s.charAt(left));
  char rightChar = Character.toLowerCase(s.charAt(right));
  if (!Character.isLetterOrDigit(leftChar)) {
    left++;
  } else if (!Character.isLetterOrDigit(rightChar)) {
    right--;
  } else {
    if (leftChar != rightChar) {
      isPalindrome = false;
      break;
    }
    left++;
    right--;
  }
}
System.out.println(isPalindrome);

medium

A. Compilation error

B. false

C. true

D. Runtime exception

Solution

1. Step 1: Understand the code logic

   The code skips non-alphanumeric characters and compares lowercase letters from both ends moving inward.

2. Step 2: Trace the string "A man, a plan, a canal: Panama"

   Ignoring spaces and punctuation, the cleaned string is "amanaplanacanalpanama" which reads the same forward and backward.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Ignoring non-alphanumeric, palindrome check = true [OK]

Hint: Ignore non-letters and compare lowercase chars [OK]

Common Mistakes:

• Not skipping non-alphanumeric characters
• Not converting characters to lowercase
• Breaking loop too early without full check

4. Identify the bug in this Java code snippet for palindrome checking:

String s = "racecar";
int left = 0, right = s.length() - 1;
boolean isPalindrome = true;
while (left <= right) {
  if (s.charAt(left) != s.charAt(right)) {
    isPalindrome = false;
    break;
  }
  left++;
  right--;
}
System.out.println(isPalindrome);

medium

A. The code does not skip non-alphanumeric characters

B. The pointers should start at 1 and length - 2

C. The loop condition should be left < right, not left <= right

D. The code does not convert characters to lowercase

Solution

1. Step 1: Analyze loop condition

   Using left <= right causes the middle character to be compared with itself unnecessarily, but it does not cause wrong result here.

2. Step 2: Check correctness of condition

   The main issue is that the code does not convert characters to lowercase, so it fails for case-insensitive palindrome checks.

3. Final Answer:

   The code does not convert characters to lowercase -> Option D

4. Quick Check:

   Case sensitivity causes incorrect palindrome detection [OK]

Hint: Convert characters to lowercase to handle case sensitivity [OK]

Common Mistakes:

• Using <= causes unnecessary middle char check
• Ignoring case sensitivity
• Not handling non-alphanumeric characters

5. Given the string s = "No lemon, no melon", which modification to the two-pointer palindrome check is necessary to correctly identify it as a palindrome?

hard

A. Convert characters to lowercase and skip non-alphanumeric characters during comparison

B. Only compare characters without any conversion or skipping

C. Reverse the string and compare directly without pointers

D. Use a stack to store characters and compare with the original

Solution

1. Step 1: Understand the string content

   The string contains spaces and uppercase letters which should be ignored or normalized for palindrome check.

2. Step 2: Modify two-pointer approach

   Convert characters to lowercase and skip non-alphanumeric characters to compare only valid letters.

3. Final Answer:

   Convert characters to lowercase and skip non-alphanumeric characters during comparison -> Option A

4. Quick Check:

   Normalize case and skip invalid chars for correct palindrome [OK]

Hint: Normalize case and ignore spaces/punctuation [OK]

Common Mistakes:

• Not ignoring spaces and punctuation
• Not converting uppercase to lowercase
• Assuming direct comparison without cleaning works