Palindrome Detection in DSA C++

Mental Model

Check if a sequence reads the same forwards and backwards by comparing matching elements from start and end.

Analogy: Like checking if a word or phrase looks the same in a mirror placed at its center.

start -> [l] -> [e] -> [v] -> [e] -> [l] -> end
indexes: 0     1     2     3     4

Dry Run Walkthrough

Input: string: "level"

Goal: Determine if the string reads the same forwards and backwards

Step 1: Compare first and last characters 'l' and 'l'

l (index 0) == l (index 4)

Why: Matching characters at both ends means it could be a palindrome

Step 2: Move inward and compare 'e' and 'e'

e (index 1) == e (index 3)

Why: Next pair also matches, continue checking

Step 3: Check middle character 'v' at index 2

v (index 2) is center, no pair needed

Why: Middle character doesn't need a pair, palindrome confirmed

Result:

String "level" is a palindrome

Annotated Code

DSA C++

#include <iostream>
#include <string>

bool isPalindrome(const std::string& s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return false; // mismatch found, not palindrome
        }
        left++; // move inward from left
        right--; // move inward from right
    }
    return true; // all pairs matched
}

int main() {
    std::string input = "level";
    if (isPalindrome(input)) {
        std::cout << "String \"" << input << "\" is a palindrome" << std::endl;
    } else {
        std::cout << "String \"" << input << "\" is not a palindrome" << std::endl;
    }
    return 0;
}

while (left < right) {

loop to compare characters from both ends moving inward

if (s[left] != s[right]) {

check if characters at current pointers differ

return false; // mismatch found, not palindrome

stop early if mismatch detected

left++; // move inward from left

advance left pointer to next character

right--; // move inward from right

move right pointer inward to next character

return true; // all pairs matched

all pairs matched, confirm palindrome

Output

String "level" is a palindrome

Complexity Analysis

Time: O(n) because we compare pairs of characters from start and end once each

Space: O(1) because only two pointers are used regardless of input size

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

Edge Cases

empty string

returns true since empty string reads the same forwards and backwards

DSA C++

while (left < right) {

single character string

returns true because a single character is always a palindrome

DSA C++

while (left < right) {

string with mismatched characters

returns false as soon as mismatch is found

DSA C++

if (s[left] != s[right]) {

When to Use This Pattern

When you need to check if a sequence reads the same forwards and backwards, use two pointers moving inward from both ends to compare pairs.

Common Mistakes

Mistake: Comparing characters without moving pointers inward, causing infinite loop
Fix: Increment left and decrement right pointers inside the loop after successful comparison

Mistake: Not stopping early on mismatch and checking entire string unnecessarily
Fix: Return false immediately when a mismatch is found

Summary

Checks if a string reads the same forwards and backwards by comparing pairs of characters from both ends.

Use when you want to verify if a word or sequence is a palindrome efficiently.

The key insight is to use two pointers moving inward to compare matching characters and stop early on mismatch.

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