Palindrome Detection in DSA C

Mental Model

A palindrome reads the same forwards and backwards. We check if the first and last characters match, then move inward.

Analogy: Like checking if a word on a mirror looks the same from both sides, comparing letters from outside to inside.

string: h -> e -> l -> l -> o -> null
indexes: [0] -> [1] -> [2] -> [3] -> [4]

Dry Run Walkthrough

Input: string: 'radar'

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

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

'r' == 'r', continue checking inside

Why: Matching outer characters means palindrome is still possible

Step 2: Compare second and second last characters 'a' and 'a'

'a' == 'a', continue checking inside

Why: Matching next pair keeps palindrome condition

Step 3: Compare middle character 'd' with itself

Middle reached, no mismatch found

Why: Single middle character always matches itself

Result:

'r' -> 'a' -> 'd' -> 'a' -> 'r' -> null
Palindrome detected: true

Annotated Code

DSA C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isPalindrome(char str[]) {
    int left = 0;
    int right = strlen(str) - 1;

    while (left < right) {
        if (str[left] != str[right]) {
            return false; // mismatch found, not palindrome
        }
        left++; // move inward from left
        right--; // move inward from right
    }
    return true; // all matched, palindrome
}

int main() {
    char input[] = "radar";
    if (isPalindrome(input)) {
        printf("%s -> Palindrome detected\n", input);
    } else {
        printf("%s -> Not a palindrome\n", input);
    }
    return 0;
}

while (left < right) {

loop to compare characters from outside moving inward

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

check for mismatch to stop early

left++;

advance left pointer inward

right--;

advance right pointer inward

return true;

all pairs matched, confirm palindrome

Output

radar -> Palindrome detected

Complexity Analysis

Time: O(n) because we compare pairs from both ends once until the middle

Space: O(1) because we use only two pointers and no extra storage

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

Edge Cases

empty string

returns true since empty string reads same forwards and backwards

DSA C

while (left < right) {

single character string

returns true because single character is palindrome

DSA C

while (left < right) {

string with mismatch at start

returns false immediately on first mismatch

DSA C

if (str[left] != str[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 to detect palindrome efficiently.

Common Mistakes

Mistake: Comparing characters without moving pointers inward
Fix: Increment left and decrement right pointers after each successful comparison

Mistake: Not stopping early on mismatch
Fix: Return false immediately when a mismatch is found

Summary

Checks if a string reads the same forwards and backwards.

Use when you want to verify palindrome property efficiently.

Compare characters from outside moving inward, stop early on mismatch.