Valid Palindrome Two Pointer in DSA C++ - Execution Trace

Concept Flow - Valid Palindrome Two Pointer

Start with two pointers

↓

Check if left < right?

No→End: Palindrome

Yes↓

Skip non-alphanumeric at left

↓

Skip non-alphanumeric at right

↓

Compare characters at left and right

↓

Return False

↓

Move left++ and right--

↩Back to Check

Two pointers start at the string ends, skip non-letters/numbers, compare characters, move inward until pointers cross or mismatch.

Execution Sample

DSA C++

bool isPalindrome(string s) {
  int left = 0, right = s.size() - 1;
  while (left < right) {
    if (!isalnum(s[left])) left++;
    else if (!isalnum(s[right])) right--;
    else if (tolower(s[left]) != tolower(s[right])) return false;
    else { left++; right--; }
  }
  return true;
}

Checks if a string is a palindrome ignoring cases and non-alphanumeric characters using two pointers.

Execution Table

Step	Operation	left	right	Characters Compared	Action	Result
1	Initialize pointers	0	10	-	Start	Continue
2	Check s[left] = 'A' (alnum?)	0	10	-	Yes	Continue
3	Check s[right] = 'a' (alnum?)	0	10	-	Yes	Continue
4	Compare 'A' and 'a'	0	10	'A' vs 'a'	Match (case-insensitive)	Move left++ and right--
5	Pointers updated	1	9	-	-	Continue
6	Check s[left] = ',' (alnum?)	1	9	-	No	left++
7	Pointers updated	2	9	-	-	Continue
8	Check s[left] = 'm' (alnum?)	2	9	-	Yes	Continue
9	Check s[right] = 'M' (alnum?)	2	9	-	Yes	Continue
10	Compare 'm' and 'M'	2	9	'm' vs 'M'	Match (case-insensitive)	Move left++ and right--
11	Pointers updated	3	8	-	-	Continue
12	Check s[left] = 'a' (alnum?)	3	8	-	Yes	Continue
13	Check s[right] = 'a' (alnum?)	3	8	-	Yes	Continue
14	Compare 'a' and 'a'	3	8	'a' vs 'a'	Match	Move left++ and right--
15	Pointers updated	4	7	-	-	Continue
16	Check s[left] = 'n' (alnum?)	4	7	-	Yes	Continue
17	Check s[right] = 'n' (alnum?)	4	7	-	Yes	Continue
18	Compare 'n' and 'n'	4	7	'n' vs 'n'	Match	Move left++ and right--
19	Pointers updated	5	6	-	-	Continue
20	Check s[left] = ',' (alnum?)	5	6	-	No	left++
21	Pointers updated	6	6	-	-	Continue
22	Check if left < right	6	6	-	No	End: Palindrome
23	Return	-	-	-	-	true

💡 Pointers crossed or met (left=6, right=6), all compared characters matched, so string is palindrome.

Variable Tracker

Variable	Start	After Step 4	After Step 10	After Step 14	After Step 18	After Step 21	Final
left	0	1	3	4	5	6	6
right	10	9	8	7	6	6	6

Key Moments - 3 Insights

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

Because the palindrome check ignores punctuation and spaces. See steps 6 and 20 where left pointer skips ',' to compare only alphanumeric characters.

Why do we compare characters in lowercase?

To ignore case differences. At steps 4 and 10, 'A' and 'a' or 'm' and 'M' match because we convert both to lowercase before comparing.

When do we stop the loop?

When left pointer is no longer less than right pointer (step 22), meaning all pairs have been checked successfully.

Visual Quiz - 3 Questions

Look at the execution table, what are the values of left and right pointers after step 10?

A left=1, right=9

B left=2, right=9

C left=3, right=8

D left=0, right=10

💡 Hint

Check the 'Pointers updated' row after step 10 in the execution_table.

At which step does the left pointer skip a non-alphanumeric character for the first time?

A Step 2

B Step 6

C Step 20

D Step 14

💡 Hint

Look for the first 'No' in 'Check s[left] (alnum?)' and the action 'left++' in execution_table.

If the string had a mismatch at characters compared in step 14, what would happen?

A The function would return true

B The pointers would move inward

C The function would return false

D The loop would continue without changes

💡 Hint

Refer to step 4 where a mismatch causes immediate return false.

Concept Snapshot

Two pointers start at string ends.
Skip non-alphanumeric characters.
Compare characters case-insensitively.
If mismatch, return false.
If pointers cross, return true.
Efficient palindrome check ignoring punctuation and case.

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 numbers. 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 or meet 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 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