Palindrome Detection in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Palindrome Check Function

What is the output of the following C++ code that checks if a string is a palindrome?

DSA C++

#include <iostream>
#include <string>

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

int main() {
    std::string test = "racecar";
    if (isPalindrome(test))
        std::cout << "Palindrome" << std::endl;
    else
        std::cout << "Not Palindrome" << std::endl;
    return 0;
}

A Runtime error

B "Not Palindrome"

C Compilation error

D "Palindrome"

💡 Hint

Check if the string reads the same forwards and backwards.

The function compares characters from start and end moving towards the center. Since "racecar" is the same forwards and backwards, it returns true and prints "Palindrome".

🧠 Conceptual

intermediate

Understanding Palindrome Detection Logic

Which statement best describes the logic used in a two-pointer palindrome detection approach?

A Compare characters from the start and end moving towards the center, stopping if a mismatch is found.

B Reverse the string and compare it to the original string.

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

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

💡 Hint

Think about how two pointers can check characters efficiently.

The two-pointer method compares characters from both ends moving inward, stopping early if characters differ, which is efficient for palindrome detection.

❓ Predict Output

advanced

Output of Palindrome Check with Mixed Case and Spaces

What is the output of this C++ code that checks if a string is a palindrome ignoring case and spaces?

DSA C++

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

bool isPalindrome(const std::string& s) {
    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])) return false;
        left++;
        right--;
    }
    return true;
}

int main() {
    std::string test = "A man, a plan, a canal, Panama";
    if (isPalindrome(test))
        std::cout << "Palindrome" << std::endl;
    else
        std::cout << "Not Palindrome" << std::endl;
    return 0;
}

A "Palindrome"

B "Not Palindrome"

C Compilation error

D Runtime error

💡 Hint

Ignore spaces and case when comparing characters.

The code skips non-alphanumeric characters and compares letters ignoring case. The phrase "A man, a plan, a canal, Panama" is a palindrome under these rules.

🔧 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++

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

A Always returns true

B Returns false for all strings

C Runtime error: out-of-range access

D Compilation error due to missing return statement

💡 Hint

Check how the right pointer is initialized and used.

The right pointer is initialized to s.size(), which is one past the last valid index, causing out-of-range access and runtime error.

🚀 Application

expert

Count Palindromic Substrings in a String

Given the following C++ code, what is the value of variable count after execution?

DSA C++

#include <iostream>
#include <string>

int countPalindromicSubstrings(const std::string& s) {
    int n = s.size();
    int count = 0;
    for (int center = 0; center < 2*n - 1; ++center) {
        int left = center / 2;
        int right = left + center % 2;
        while (left >= 0 && right < n && s[left] == s[right]) {
            count++;
            left--;
            right++;
        }
    }
    return count;
}

int main() {
    std::string test = "aaa";
    int count = countPalindromicSubstrings(test);
    std::cout << count << std::endl;
    return 0;
}

A 4

B 6

C 3

D 5

💡 Hint

Count all palindromic substrings including single characters and overlapping ones.

The string "aaa" has palindromic substrings: "a", "a", "a", "aa", "aa", "aaa" totaling 6.

Practice

1. What does a palindrome string mean in simple terms?

easy

A. A string that has all unique characters

B. A string that reads the same forwards and backwards

C. A string that contains only vowels

D. A string that ends with a special character

Solution

1. Step 1: Understand palindrome definition

   A palindrome is a word or phrase that reads the same from left to right and right to left.

2. Step 2: Compare options with definition

   Only "A string that reads the same forwards and backwards" matches this meaning exactly.

3. Final Answer:

   A string that reads the same forwards and backwards -> Option B

4. Quick Check:

   Palindrome = same forwards and backwards [OK]

Hint: Palindrome means same forwards and backwards [OK]

Common Mistakes:

• Confusing palindrome with unique characters
• Thinking palindrome means only vowels
• Assuming palindrome ends with special character

2. Which of the following C++ code snippets correctly checks if a string s is a palindrome?

easy

A. for (int i = 0; i < s.size() / 2; i++) if (s[i] != s[s.size() - i - 1]) return false;

B. for (int i = 0; i < s.size(); i++) if (s[i] == s[i + 1]) return true;

C. for (int i = 0; i < s.size(); i++) if (s[i] != s[i + 1]) return false;

D. for (int i = 1; i <= s.size(); i++) if (s[i] != s[s.size() - i]) return false;

Solution

1. Step 1: Analyze loop and index usage

   for (int i = 0; i < s.size() / 2; i++) if (s[i] != s[s.size() - i - 1]) return false; correctly loops till half the string and compares characters from start and end.

2. Step 2: Check correctness of index calculations

   for (int i = 0; i < s.size() / 2; i++) if (s[i] != s[s.size() - i - 1]) return false; uses s.size() - i - 1 which is correct for zero-based indexing.

3. Final Answer:

   for (int i = 0; i < s.size() / 2; i++) if (s[i] != s[s.size() - i - 1]) return false; -> Option A

4. Quick Check:

   Correct index and loop range = for (int i = 0; i < s.size() / 2; i++) if (s[i] != s[s.size() - i - 1]) return false; [OK]

Hint: Check characters from start and end up to middle [OK]

Common Mistakes:

• Using wrong loop range (full length instead of half)
• Incorrect index calculation causing out-of-range errors
• Comparing adjacent characters instead of mirrored ones

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

std::string s = "racecar";
bool isPalindrome = true;
for (int i = 0; i < s.size() / 2; i++) {
  if (s[i] != s[s.size() - i - 1]) {
    isPalindrome = false;
    break;
  }
}
std::cout << (isPalindrome ? "Yes" : "No") << std::endl;

medium

A. Yes

B. No

C. Compilation error

D. Runtime error

Solution

1. Step 1: Understand the string and loop

   The string "racecar" is a palindrome because it reads the same forwards and backwards.

2. Step 2: Trace the loop comparisons

   The loop compares characters from start and end; all pairs match, so isPalindrome remains true.

3. Final Answer:

   Yes -> Option A

4. Quick Check:

   "racecar" is palindrome = Yes [OK]

Hint: Check mirrored characters; all match means palindrome [OK]

Common Mistakes:

• Assuming "racecar" is not palindrome
• Confusing output strings
• Ignoring break statement in loop

4. Find the error in this palindrome check code snippet:

bool checkPalindrome(std::string s) {
  for (int i = 0; i <= s.size() / 2; i++) {
    if (s[i] != s[s.size() - i]) {
      return false;
    }
  }
  return true;
}

medium

A. Comparison should be s[i] == s[s.size() - i]

B. No error, code works fine

C. Function should return void instead of bool

D. End index should be s[s.size() - i - 1] instead of s[s.size() - i] to avoid out-of-range

Solution

1. Step 1: Check loop range and indexing

   The end index s[s.size() - i] for i=0 accesses s[s.size()], causing out-of-range error.

2. Step 2: Correct index calculation

   Change to s[s.size() - i - 1] for proper zero-based end index mirroring.

3. Final Answer:

   End index should be s[s.size() - i - 1] instead of s[s.size() - i] to avoid out-of-range -> Option D

4. Quick Check:

   End index = size - i - 1 [OK]

Hint: End index: s.size() - i - 1 [OK]

Common Mistakes:

• Wrong end index s[size - i] causes out-of-bound access
• Confusing equality and inequality in comparisons
• Ignoring return type correctness

5. You want to check if a sentence is a palindrome ignoring spaces, punctuation, and case. Which approach is best?

hard

A. Only convert to lowercase and check palindrome

B. Check palindrome directly on original string without changes

C. Remove non-alphanumeric characters, convert to lowercase, then check palindrome

D. Reverse the string and compare without any preprocessing

Solution

1. Step 1: Understand palindrome ignoring spaces and punctuation

   To ignore spaces and punctuation, remove all non-alphanumeric characters and convert to lowercase for uniform comparison.

2. Step 2: Apply palindrome check on cleaned string

   After cleaning, check if the string reads the same forwards and backwards.

3. Final Answer:

   Remove non-alphanumeric characters, convert to lowercase, then check palindrome -> Option C

4. Quick Check:

   Clean string then check palindrome [OK]

Hint: Clean string first, then check palindrome [OK]

Common Mistakes:

• Checking palindrome without cleaning string
• Ignoring case differences
• Assuming spaces and punctuation don't affect palindrome