Palindrome Detection in DSA C - Execution Trace

Concept Flow - Palindrome Detection

Start

↓

Set left = 0, right = length-1

↓

Compare s[left

↓

Return False

Yes↓

Increment left, Decrement right

↓

Check if left >= right

↓

Return True

No↓

left

Start with two pointers at the string ends, compare characters moving inward until mismatch or pointers cross.

Execution Sample

DSA C

int isPalindrome(char *s) {
  int left = 0, right = strlen(s) - 1;
  while (left < right) {
    if (s[left] != s[right]) return 0;
    left++; right--;
  }
  return 1;
}

Checks if a string is a palindrome by comparing characters from both ends moving inward.

Execution Table

Step	Operation	left	right	Characters Compared	Match?	Action	Visual State
1	Initialize pointers	0	6	-	-	Set left=0, right=6	"r" "a" "c" "e" "c" "a" "r"
2	Compare s[left] and s[right]	0	6	r vs r	Yes	left++, right--	"r" "a" "c" "e" "c" "a" "r"
3	Compare s[left] and s[right]	1	5	a vs a	Yes	left++, right--	"r" "a" "c" "e" "c" "a" "r"
4	Compare s[left] and s[right]	2	4	c vs c	Yes	left++, right--	"r" "a" "c" "e" "c" "a" "r"
5	Compare s[left] and s[right]	3	3	e vs e	Yes	left >= right, return True	"r" "a" "c" "e" "c" "a" "r"
6	End	-	-	-	-	Palindrome detected	"r" "a" "c" "e" "c" "a" "r"

💡 Pointers crossed at step 5, all characters matched, string is palindrome

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
left	0	1	2	3	3	3
right	6	5	4	3	3	3

Key Moments - 3 Insights

Why do we stop comparing when left >= right?

Because when left meets or passes right, all pairs have been checked. See execution_table step 5 where left=3 and right=3 means middle reached.

What if characters at left and right don't match?

We immediately return false as shown in execution_table step 2-4 'Match?' column. If any mismatch occurs, palindrome check fails.

Why do we increment left and decrement right after each successful comparison?

To move inward and compare the next pair of characters, as shown in execution_table steps 2-4 'Action' column.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what are the values of left and right?

A left=2, right=4

B left=3, right=3

C left=1, right=5

D left=0, right=6

💡 Hint

Check the 'left' and 'right' columns in execution_table row with Step=3

At which step does the function decide the string is a palindrome?

A Step 5

B Step 2

C Step 4

D Step 6

💡 Hint

Look at the 'Action' column where it returns True when left >= right

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

A Characters match, continue

B Characters don't match, return false

C Pointers cross, return true

D Error due to string length

💡 Hint

Refer to 'Match?' column in execution_table for mismatch behavior

Concept Snapshot

Palindrome Detection:
- Use two pointers: left at start, right at end
- Compare characters s[left] and s[right]
- If mismatch, return false immediately
- If pointers cross or meet, return true
- Moves inward by left++ and right-- each step

Full Transcript

Palindrome detection uses two pointers starting at the ends of the string. We compare characters at these pointers. If they match, we move the pointers inward. If any pair does not match, the string is not a palindrome. When the pointers meet or cross, it means all pairs matched and the string is a palindrome.

Practice

1. What is a palindrome in the context of strings?

easy

A. A string that contains only vowels

B. A string that ends with a special character

C. A string with all unique characters

D. A string that reads the same forwards and backwards

Solution

1. Step 1: Understand palindrome definition

   A palindrome is a word or phrase that reads the same forwards and backwards, ignoring spaces and punctuation.

2. Step 2: Compare options with definition

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

3. Final Answer:

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

4. Quick Check:

   Palindrome = same forwards and backwards [OK]

Hint: Check if string equals its reverse [OK]

Common Mistakes:

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

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

easy

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

B. for (int i = 0; i < strlen(s); i++) { if (s[i] == s[i+1]) return 1; } return 0;

C. for (int i = 0; i < strlen(s); i++) { if (s[i] != s[i+1]) return 0; } return 1;

D. for (int i = 0; i < strlen(s)/2; i++) { if (s[i] == s[strlen(s)-1-i]) return 0; } return 1;

Solution

1. Step 1: Analyze palindrome check logic

   We compare characters from start and end moving towards center. If any pair differs, string is not palindrome.

2. Step 2: Match code with logic

   for (int i = 0; i < strlen(s)/2; i++) { if (s[i] != s[strlen(s)-1-i]) return 0; } return 1; correctly compares s[i] and s[length-1-i] for half the string length and returns 0 if mismatch found, else 1.

3. Final Answer:

   for (int i = 0; i < strlen(s)/2; i++) { if (s[i] != s[strlen(s)-1-i]) return 0; } return 1; -> Option A

4. Quick Check:

   Compare front and back chars for half length [OK]

Hint: Check characters from ends moving inward [OK]

Common Mistakes:

• Comparing adjacent characters instead of opposite ends
• Returning 1 too early inside loop
• Incorrect loop range causing out-of-bounds

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

char s[] = "radar";
int i, flag = 1;
int n = strlen(s);
for (i = 0; i < n/2; i++) {
  if (s[i] != s[n - i - 1]) {
    flag = 0;
    break;
  }
}
printf("%d", flag);

medium

A. 0

B. 1

C. Compilation error

D. Undefined behavior

Solution

1. Step 1: Understand the code logic

   The code checks if string "radar" is palindrome by comparing characters from start and end.

2. Step 2: Trace the loop comparisons

   Characters match at all pairs: r-r, a-a, d-d (middle ignored). So flag remains 1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   "radar" is palindrome, flag = 1 [OK]

Hint: Check if string equals reverse, print 1 if yes [OK]

Common Mistakes:

• Assuming flag is 0 for palindrome
• Confusing loop range causing missed checks
• Misreading string length calculation

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

int isPalindrome(char *s) {
  int n = strlen(s);
  for (int i = 0; i <= n/2; i++) {
    if (s[i] != s[n - i]) {
      return 0;
    }
  }
  return 1;
}

medium

A. Loop condition should be i < n/2, not i <= n/2

B. Function should return void instead of int

C. Index n - i should be n - i - 1 to avoid out-of-bounds

D. No error, code works correctly

Solution

1. Step 1: Check array indexing in condition

   String indices go from 0 to n-1, so s[n - i] accesses out-of-bounds when i=0.

2. Step 2: Correct index to n - i - 1

   Changing to s[n - i - 1] fixes indexing and prevents runtime error.

3. Final Answer:

   Index n - i should be n - i - 1 to avoid out-of-bounds -> Option C

4. Quick Check:

   Array index must be within 0 to n-1 [OK]

Hint: Remember last index is length - 1 [OK]

Common Mistakes:

• Using wrong loop boundary causing extra iteration
• Ignoring off-by-one in array indexing
• Assuming function return type is incorrect

5. Given a string with mixed case and spaces, which approach correctly checks if it is a palindrome ignoring case and spaces?

char s[] = "A man a plan a canal Panama";

hard

A. Remove spaces and convert to lowercase, then check palindrome normally

B. Check palindrome directly without modifications

C. Only convert to lowercase, ignore spaces

D. Only remove spaces, ignore case

Solution

1. Step 1: Normalize string by removing spaces and converting to lowercase

   Spaces and case differences affect palindrome check, so remove spaces and convert all letters to lowercase.

2. Step 2: Perform palindrome check on normalized string

   After normalization, check if string reads same forwards and backwards.

3. Final Answer:

   Remove spaces and convert to lowercase, then check palindrome normally -> Option A

4. Quick Check:

   Normalize string before palindrome check [OK]

Hint: Clean string first: lowercase + no spaces [OK]

Common Mistakes:

• Ignoring spaces causing false negatives
• Ignoring case differences causing false negatives
• Checking palindrome on raw string directly