Valid Palindrome Two Pointer in DSA C++

Mental Model

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

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

s = "racecar"
left ↑                 right ↑
r -> a -> c -> e -> c -> a -> r -> null

Dry Run Walkthrough

Input: string: "racecar"

Goal: Determine if the string is a palindrome by comparing characters from both ends moving inward.

Step 1: Compare characters at left=0 and right=6 ('r' and 'r')

r (left=0) -> a -> c -> e -> c -> a -> r (right=6)

Why: Check if outer characters match to confirm palindrome property

Step 2: Move left to 1 and right to 5, compare 'a' and 'a'

r -> a (left=1) -> c -> e -> c -> a (right=5) -> r

Why: Continue checking inward pairs for equality

Step 3: Move left to 2 and right to 4, compare 'c' and 'c'

r -> a -> c (left=2) -> e -> c (right=4) -> a -> r

Why: Still matching, keep moving inward

Step 4: Move left to 3 and right to 3, pointers meet at 'e'

r -> a -> c -> e (left=3, right=3) -> c -> a -> r

Why: Middle character reached, all pairs matched

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <string>
#include <cctype>

bool isPalindrome(const std::string& s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        // Skip non-alphanumeric on left
        while (left < right && !std::isalnum(s[left])) {
            left++;
        }
        // Skip non-alphanumeric on right
        while (left < right && !std::isalnum(s[right])) {
            right--;
        }
        // Compare characters case-insensitively
        if (std::tolower(s[left]) != std::tolower(s[right])) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    std::string input = "racecar";
    bool result = isPalindrome(input);
    std::cout << input << "\nPalindrome: " << (result ? "true" : "false") << std::endl;
    return 0;
}

while (left < right) {

loop until pointers meet or cross

while (left < right && !std::isalnum(s[left])) { left++; }

skip non-alphanumeric characters from left

while (left < right && !std::isalnum(s[right])) { right--; }

skip non-alphanumeric characters from right

if (std::tolower(s[left]) != std::tolower(s[right])) { return false; }

compare characters ignoring case, return false if mismatch

left++; right--;

move pointers inward after successful match

Output

racecar

Palindrome: true

Complexity Analysis

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

Space: O(1) because only a few variables are used regardless of input size

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

Edge Cases

empty string

returns true because empty string reads the same forwards and backwards

DSA C++

while (left < right) {

string with only non-alphanumeric characters

skips all characters and returns true

DSA C++

while (left < right && !std::isalnum(s[left])) { left++; }

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

ignores case and punctuation, returns true

DSA C++

if (std::tolower(s[left]) != std::tolower(s[right])) { return false; }

When to Use This Pattern

When you need to check if a string reads the same forwards and backwards ignoring cases and non-letters, use two pointers from both ends moving inward to compare characters.

Common Mistakes

Mistake: Not skipping non-alphanumeric characters causing false negatives
Fix: Add loops to skip non-alphanumeric characters on both ends before comparing

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

Mistake: Stopping the loop too early or not moving pointers correctly
Fix: Ensure pointers move inward only after successful character match

Summary

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

Use when you want to verify palindrome ignoring case and non-alphanumeric characters.

The key insight is to use two pointers moving inward, skipping unwanted characters, and comparing lowercase characters.

Practice

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

easy

A. Sort the string and check if it matches the original

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

C. Reverse the string and compare with the original

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

Solution

1. Step 1: Understand 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 differ, string is not palindrome; if all match, it is 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 = Use two pointers starting from both ends and move towards the center comparing characters [OK]

Hint: Compare characters from ends moving inward [OK]

Common Mistakes:

• Trying to sort string instead of comparing characters
• Only checking half the string without pointers
• Ignoring case or non-alphanumeric characters

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

easy

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

B. int left = 1, right = s.size();

C. int left = s.size(), right = 0;

D. int left = s.size() - 1, right = 0;

Solution

1. Step 1: Identify valid pointer initialization

   Left pointer starts at 0 (first char), right pointer at last index (size - 1).

2. Step 2: Check each option

   int left = 0, right = s.size() - 1; correctly sets left=0 and right=s.size()-1; others have invalid indices.

3. Final Answer:

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

4. Quick Check:

   Pointers start at 0 and size-1 = int left = 0, right = s.size() - 1; [OK]

Hint: Left = 0, Right = length - 1 for string indices [OK]

Common Mistakes:

• Starting right pointer at s.size() (out of range)
• Swapping left and right initialization
• Starting left pointer at 1 instead of 0

3. What will be the output of the following C++ code?

std::string s = "A man, a plan, a canal: Panama";
int left = 0, right = s.size() - 1;
while (left < right) {
  while (left < right && !std::isalnum(s[left])) left++;
  while (left < right && !std::isalnum(s[right])) right--;
  if (std::tolower(s[left]) != std::tolower(s[right])) {
    std::cout << "Not Palindrome" << std::endl;
    return 0;
  }
  left++;
  right--;
}
std::cout << "Palindrome" << std::endl;

medium

A. Compilation Error

B. Not Palindrome

C. Runtime Error

D. Palindrome

Solution

1. Step 1: Understand the code logic

   It skips non-alphanumeric chars and compares characters case-insensitively from both ends.

2. Step 2: Check if string is palindrome ignoring cases and symbols

   "A man, a plan, a canal: Panama" is a classic palindrome ignoring spaces and punctuation.

3. Final Answer:

   Palindrome -> Option D

4. Quick Check:

   Ignoring non-alnum and case, string is palindrome = Palindrome [OK]

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

Common Mistakes:

• Not skipping non-alphanumeric characters
• Comparing characters case-sensitively
• Confusing output with runtime or compile errors

4. Identify the bug in this palindrome check code snippet:

std::string s = "racecar";
int left = 0, right = s.size();
while (left < right) {
  if (s[left] != s[right]) {
    std::cout << "Not Palindrome" << std::endl;
    break;
  }
  left++;
  right--;
}
std::cout << "Palindrome" << std::endl;

medium

A. Right pointer initialized to s.size() which is out of range

B. Left pointer should start at 1

C. Missing tolower() for case-insensitive check

D. Loop condition should be left <= right

Solution

1. Step 1: Check pointer initialization

   Right pointer is set to s.size(), which is one past the last valid index.

2. Step 2: Understand consequences

   Accessing s[right] causes out-of-bounds error or undefined behavior.

3. Final Answer:

   Right pointer initialized to s.size() which is out of range -> Option A

4. Quick Check:

   Right pointer must be s.size()-1, not s.size() [OK]

Hint: Right pointer = length - 1 to avoid out-of-range [OK]

Common Mistakes:

• Using s.size() as last index
• Ignoring out-of-bounds access errors
• Assuming loop condition fixes index error

5. Given a string s, how would you modify the two-pointer palindrome check to ignore spaces, punctuation, and be case-insensitive? Choose the best approach.

hard

A. Convert string to uppercase and compare characters including spaces

B. Reverse the string and compare directly without any changes

C. Use two pointers; skip non-alphanumeric chars; compare lowercase characters

D. Count characters frequency and check if all are even

Solution

1. Step 1: Handle non-alphanumeric characters

   Skip spaces and punctuation by moving pointers until alphanumeric chars found.

2. Step 2: Compare characters case-insensitively

   Convert characters to lowercase before comparing to ignore case differences.

3. Final Answer:

   Use two pointers; skip non-alphanumeric chars; compare lowercase characters -> Option C

4. Quick Check:

   Skip non-alnum + lowercase compare = Use two pointers; skip non-alphanumeric chars; compare lowercase characters [OK]

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

Common Mistakes:

• Comparing characters without skipping punctuation
• Ignoring case differences
• Using frequency count which doesn't check order