Valid Palindrome Two Pointer in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Two Pointer Palindrome Check

What is the output of the following C++ code that checks if a string is a palindrome ignoring non-alphanumeric characters and case?

DSA C++

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

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

int main() {
    string test = "A man, a plan, a canal: Panama";
    cout << (isPalindrome(test) ? "true" : "false") << endl;
    return 0;
}

A false

B Runtime error

C Compilation error

D true

💡 Hint

Focus on how non-alphanumeric characters are skipped and case is ignored.

The code uses two pointers moving inward, skipping non-alphanumeric characters and comparing lowercase characters. The input string is a well-known palindrome phrase ignoring punctuation and case, so the output is true.

❓ Predict Output

intermediate

Result of Palindrome Check on Mixed Characters

What will be the output of this C++ code snippet?

DSA C++

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

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

int main() {
    string test = "race a car";
    cout << (isPalindrome(test) ? "true" : "false") << endl;
    return 0;
}

A true

B Compilation error

C false

D Runtime error

💡 Hint

Check if the characters match after skipping spaces and ignoring case.

The string "race a car" is not a palindrome when ignoring spaces and case because 'e' and 'a' do not match at the corresponding positions.

🔧 Debug

advanced

Identify the Error in Palindrome Function

What error will this C++ code produce when checking if a string is a palindrome?

DSA C++

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

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

A No error, returns correct result

B Runtime error due to out-of-bounds access

C Compilation error due to missing headers

D Logical error, always returns false

💡 Hint

Check how the pointers move when skipping non-alphanumeric characters.

The code increments left and right pointers without proper checks after skipping non-alphanumeric characters, which can cause out-of-bounds access when left or right moves beyond limits.

🧠 Conceptual

advanced

Why Use Two Pointers for Palindrome Check?

Why is the two-pointer technique efficient for checking if a string is a palindrome ignoring non-alphanumeric characters and case?

A It allows checking characters from both ends simultaneously, skipping irrelevant characters efficiently.

B It sorts the string first to compare characters easily.

C It converts the string to uppercase and compares only the first half.

D It uses extra memory to store a reversed string for comparison.

💡 Hint

Think about how two pointers move and what they compare.

Two pointers start from the beginning and end, moving inward while skipping non-alphanumeric characters, allowing efficient comparison without extra space or sorting.

❓ Predict Output

expert

Output of Palindrome Check with Unicode Characters

What is the output of this C++ code that checks palindrome for a string containing Unicode characters?

DSA C++

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

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

int main() {
    string test = "ÀbççbÀ";
    cout << (isPalindrome(test) ? "true" : "false") << endl;
    return 0;
}

A false

B true

C Compilation error due to Unicode

D Runtime error due to Unicode

💡 Hint

Consider how tolower and isalnum behave with Unicode characters in standard C++.

Standard C++ functions like tolower and isalnum do not handle Unicode characters correctly, so the comparison fails and the function returns false.

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