Palindrome Detection in DSA C++ - Execution Trace

Concept Flow - Palindrome Detection

Start with input string

↓

Set left pointer at start

↓

Set right pointer at end

↓

Compare characters at left and right

↓

Return False: Not palindrome

Yes↓

Move left pointer right

↓

Move right pointer left

↓

Left pointer >= Right pointer?

No→Repeat comparison

Yes↓

Return True: Is palindrome

We use two pointers starting at the ends of the string, compare characters moving inward until pointers meet or mismatch is found.

Execution Sample

DSA C++

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

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

Execution Table

Step	Operation	Left Pointer	Right Pointer	Characters Compared	Match?	Action	Result So Far
1	Initialize pointers	0	6	-	-	Start comparing	Undecided
2	Compare s[0] and s[6]	0	6	'r' vs 'r'	Yes	Move pointers inward	Undecided
3	Update pointers	1	5	-	-	-	Undecided
4	Compare s[1] and s[5]	1	5	'a' vs 'a'	Yes	Move pointers inward	Undecided
5	Update pointers	2	4	-	-	-	Undecided
6	Compare s[2] and s[4]	2	4	'c' vs 'c'	Yes	Move pointers inward	Undecided
7	Update pointers	3	3	-	-	-	Undecided
8	Check pointers	3	3	-	-	Left >= Right, stop	Palindrome confirmed
9	Return result	-	-	-	-	Return true	Palindrome

💡 Left pointer reached or passed right pointer, all compared characters matched

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
left	0	1	2	3	3	3
right	6	5	4	3	3	3
result	Undecided	Undecided	Undecided	Undecided	Palindrome confirmed	Palindrome

Key Moments - 3 Insights

Why do we stop comparing when left pointer is equal to or greater than right pointer?

Because when left >= right, all pairs have been checked and matched (see execution_table step 8), so the string is confirmed palindrome.

What happens if characters at left and right pointers do not match?

The function immediately returns false (not palindrome), as shown in execution_table step 2 condition 'Match?' No branch.

Why do we move left pointer forward and right pointer backward after each successful comparison?

To compare the next inner pair of characters, moving towards the center, as shown in steps 3, 5, and 7 updating pointers.

Visual Quiz - 3 Questions

Look at the execution_table, what characters are compared at step 6?

A 'c' vs 'c'

B 'a' vs 'a'

C 'r' vs 'r'

D 'd' vs 'd'

💡 Hint

Check the 'Characters Compared' column at step 6 in execution_table.

At which step does the left pointer become equal to the right pointer?

A Step 4

B Step 6

C Step 8

D Step 9

💡 Hint

Look at the 'Left Pointer' and 'Right Pointer' columns in execution_table rows.

If the string was 'racecarx', what would happen at step 2?

A Characters match, continue

B Characters do not match, return false

C Pointers move inward without comparison

D Function returns true immediately

💡 Hint

Recall the 'Match?' column and action when characters differ in execution_table step 2.

Concept Snapshot

Palindrome Detection:
- Use two pointers: left at start, right at end
- Compare characters at left and right
- If mismatch, return false immediately
- Move pointers inward if match
- Stop when left >= right
- Return true if all matched

Full Transcript

Palindrome detection checks if a string reads the same forwards and backwards. We start with two pointers: one at the beginning (left) and one at the end (right) of the string. We compare the characters at these pointers. If they match, we move the left pointer one step right and the right pointer one step left, then compare again. If at any point the characters do not match, we return false immediately because the string is not a palindrome. We continue this process until the left pointer is equal to or passes the right pointer, which means all character pairs matched and the string is a palindrome, so we return true.

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