Valid Palindrome Two Pointer in DSA C

Mental Model

Use two pointers starting from both ends of the string and move towards the center, comparing characters to check if the string reads the same forwards and backwards.

Analogy: Imagine two friends starting at opposite ends of a hallway, walking towards each other while checking if the tiles under their feet match. If all matching tiles are the same, the hallway is symmetrical.

s = "racecar"

Indices: 0 1 2 3 4 5 6
String: r a c e c a r
Pointers:
left ↑                 right ↑

Dry Run Walkthrough

Input: string: "racecar"

Goal: Check if the string is a palindrome by comparing characters from both ends moving inward.

Step 1: Compare characters at left=0 and right=6 ('r' and 'r')

r [left->r] a c e c a [right->r]
Pointers move inward: left=1, right=5

Why: Characters match, so continue checking inner characters

Step 2: Compare characters at left=1 and right=5 ('a' and 'a')

r a [left->a] c e c [right->a] r
Pointers move inward: left=2, right=4

Why: Characters match, continue checking

Step 3: Compare characters at left=2 and right=4 ('c' and 'c')

r a c [left->c] e [right->c] a r
Pointers move inward: left=3, right=3

Why: Characters match, continue checking

Step 4: Pointers meet at left=3 and right=3 ('e')

r a c e [left->e,right->e] c a r
Pointers crossed or met, all checks passed

Why: Middle character reached, string is palindrome

Result:

r a c e c a r
Palindrome: true

Annotated Code

DSA C

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

bool isPalindrome(char *s) {
    int left = 0;
    int right = strlen(s) - 1;

    while (left < right) {
        // Skip non-alphanumeric on left
        while (left < right && !isalnum(s[left])) {
            left++;
        }
        // Skip non-alphanumeric on right
        while (left < right && !isalnum(s[right])) {
            right--;
        }
        // Compare characters case-insensitively
        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    char s[] = "racecar";
    if (isPalindrome(s)) {
        printf("%s\nPalindrome: true\n", s);
    } else {
        printf("%s\nPalindrome: false\n", s);
    }
    return 0;
}

while (left < right) {

loop until pointers meet or cross

while (left < right && !isalnum(s[left])) { left++; }

skip non-alphanumeric characters from left

while (left < right && !isalnum(s[right])) { right--; }

skip non-alphanumeric characters from right

if (tolower(s[left]) != tolower(s[right])) { return false; }

compare characters ignoring case, return false if mismatch

left++; right--;

move pointers inward to check next characters

Output

racecar

Palindrome: true

Complexity Analysis

Time: O(n) because we scan the string once with two pointers moving inward

Space: O(1) because we use only a few variables regardless of input size

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

Edge Cases

empty string

returns true because empty string reads the same forwards and backwards

DSA C

while (left < right) {

string with only non-alphanumeric characters

skips all characters and returns true

DSA C

while (left < right && !isalnum(s[left])) { left++; }

string with mixed case and punctuation, e.g. "A man, a plan, a canal: Panama"

ignores case and non-alphanumeric, returns true

DSA C

if (tolower(s[left]) != tolower(s[right])) { return false; }

When to Use This Pattern

When you need to check if a string reads the same forwards and backwards ignoring cases and symbols, use the two pointer pattern to compare characters from both ends efficiently.

Common Mistakes

Mistake: Not skipping non-alphanumeric characters causing wrong mismatch
Fix: Add loops to skip non-alphanumeric characters before comparing

Mistake: Comparing characters without ignoring case
Fix: Use tolower() or toupper() to compare characters case-insensitively

Mistake: Moving pointers incorrectly causing infinite loop or missed checks
Fix: Increment left and decrement right only after successful comparison

Summary

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

Use when you want to verify palindrome ignoring case and non-alphanumeric characters efficiently.

The key insight is to use two pointers moving inward and skip irrelevant characters before comparing.