Valid Palindrome Two Pointer in DSA Java - Execution Trace

Concept Flow - Valid Palindrome Two Pointer

Start: left=0, right=length-1

↓

Check if left < right?

No→Return True

Yes↓

Skip non-alphanumeric at left

↓

Skip non-alphanumeric at right

↓

Compare chars at left and right

↓

left++, right--

↓

Repeat loop

Two pointers start at the string ends, skip non-letters/numbers, compare characters, move inward if equal, else return false.

Execution Sample

DSA Java

public boolean isPalindrome(String s) {
  int left = 0, right = s.length() - 1;
  while (left < right) {
    while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
    while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
    if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
    left++; right--;
  }
  return true;
}

Checks if a string is a palindrome ignoring non-alphanumeric characters and case by using two pointers moving inward.

Execution Table

Step	Operation	left	right	Chars Compared	Comparison Result	Action	String State
1	Initialize pointers	0	10			Start loop	"A m,a n n a m a"
2	Skip non-alphanumeric left	0	10			left stays at 'A'	"A m,a n n a m a"
3	Skip non-alphanumeric right	0	10			right stays at 'a'	"A m,a n n a m a"
4	Compare chars	0	10	'A' vs 'a'	Equal (case-insensitive)	left++, right--	"A m,a n n a m a"
5	Skip non-alphanumeric left	1	9			left moves to 'm'	"A m,a n n a m a"
6	Skip non-alphanumeric right	1	9			right stays at 'm'	"A m,a n n a m a"
7	Compare chars	1	9	'm' vs 'm'	Equal	left++, right--	"A m,a n n a m a"
8	Skip non-alphanumeric left	2	8			left moves to 'a'	"A m,a n n a m a"
9	Skip non-alphanumeric right	2	8			right stays at 'a'	"A m,a n n a m a"
10	Compare chars	2	8	'a' vs 'a'	Equal	left++, right--	"A m,a n n a m a"
11	Skip non-alphanumeric left	3	7			left moves to 'n'	"A m,a n n a m a"
12	Skip non-alphanumeric right	3	7			right stays at 'n'	"A m,a n n a m a"
13	Compare chars	3	7	'n' vs 'n'	Equal	left++, right--	"A m,a n n a m a"
14	Pointers crossed	4	6			left >= right, loop ends	"A m,a n n a m a"
15	Return					Return true - string is palindrome

💡 left pointer crossed right pointer, all compared chars matched ignoring case and non-alphanumeric chars

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 10	After Step 13	After Step 14
left	0	1	2	3	4	4
right	10	9	8	7	6	6

Key Moments - 3 Insights

Why do we skip characters that are not letters or digits?

Because the palindrome check ignores spaces, punctuation, and symbols. See steps 5 and 8 where left pointer moves past spaces and commas before comparing.

Why do we compare characters in lowercase?

To ignore case differences. For example, 'A' and 'a' are considered equal at step 4, so we convert both to lowercase before comparing.

When does the loop stop?

The loop stops when left pointer is no longer less than right pointer, meaning all pairs have been checked. This happens at step 14.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what characters are compared?

A 'A' and 'a'

B 'm' and 'm'

C 'n' and 'n'

D 'a' and 'a'

💡 Hint

Check the 'Chars Compared' column at step 4 in the execution_table.

At which step do the left and right pointers cross, ending the loop?

A Step 10

B Step 13

C Step 14

D Step 15

💡 Hint

Look for the step where 'Pointers crossed' is noted in the 'Operation' column.

If the string had a non-alphanumeric character at the start, how would the left pointer behave?

A It would stay at 0 and compare immediately

B It would move forward skipping non-alphanumeric characters

C It would move backward

D It would cause an error

💡 Hint

See step 5 where left pointer skips spaces before comparing.

Concept Snapshot

Two pointers start at string ends
Skip non-alphanumeric chars moving inward
Compare lowercase chars at pointers
If mismatch, return false
If pointers cross, return true
Checks palindrome ignoring case and symbols

Full Transcript

This concept uses two pointers starting at the beginning and end of the string. Each pointer moves inward, skipping characters that are not letters or digits. The characters at the pointers are compared in lowercase to ignore case differences. If any pair does not match, the function returns false immediately. If the pointers cross without mismatches, the string is a palindrome and the function returns true.

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