Valid Palindrome Two Pointer in DSA Java - Build from Scratch

Valid Palindrome Two Pointer

📖 Scenario: Imagine you are building a simple text checker that tells if a word or sentence reads the same forwards and backwards, ignoring spaces, punctuation, and letter case. This is called a palindrome.For example, "Race car" is a palindrome because if you ignore spaces and case, it reads the same backwards.

🎯 Goal: You will write a Java program that uses two pointers to check if a given string is a valid palindrome. The program will ignore non-letter characters and case differences.

📋 What You'll Learn

Create a string variable with the exact value "A man, a plan, a canal: Panama"

Create two integer pointers called left and right to scan the string from both ends

Use a loop to move the pointers inward, skipping non-alphanumeric characters

Compare characters ignoring case to check palindrome validity

Print true if the string is a palindrome, otherwise false

💡 Why This Matters

🌍 Real World

Palindrome checks are useful in text processing, data validation, and coding challenges.

💼 Career

Understanding two-pointer techniques helps in solving string and array problems efficiently in software development.

1

Create the input string

Create a string variable called s and set it to the exact value "A man, a plan, a canal: Panama"

DSA Java

# Your code here

Hint

Use String s = "A man, a plan, a canal: Panama"; to create the input string.

2

Initialize two pointers

Add two integer variables called left and right. Set left to 0 and right to s.length() - 1

DSA Java

public class Main {
    public static void main(String[] args) {
        String s = "A man, a plan, a canal: Panama";
        // Initialize left and right pointers
        
    }
}

Hint

Use int left = 0; and int right = s.length() - 1; to set pointers at the start and end.

3

Use two pointers to check palindrome

Write a while loop that runs while left < right. Inside the loop, skip characters that are not letters or digits by moving left forward or right backward. Then compare characters at left and right ignoring case. If they differ, print false and return. Otherwise, move both pointers inward.

DSA Java

public class Main {
    public static void main(String[] args) {
        String s = "A man, a plan, a canal: Panama";
        int left = 0;
        int right = s.length() - 1;
        // Use while loop with two pointers to check palindrome
        
    }
}

Hint

Use nested while loops to skip non-alphanumeric characters and compare characters ignoring case.

4

Print true if palindrome

After the loop ends, print true to show the string is a valid palindrome

DSA Java

public class Main {
    public static void main(String[] args) {
        String s = "A man, a plan, a canal: Panama";
        int left = 0;
        int 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))) {
                System.out.println(false);
                return;
            }
            left++;
            right--;
        }
        // Print true here
    }
}

Hint

Print true after the loop if no mismatches were found.

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