Longest Palindromic Substring in DSA C

Mental Model

Find the longest part of a string that reads the same forwards and backwards by checking around each character.

Analogy: Like looking for the biggest mirror reflection in a line of letters, starting from each letter and expanding outwards to see how far the reflection goes.

s = "b a n a n a"
indexes: 0 1 2 3 4 5
Check centers:
  ↑
  b
  a
  n
  a
  n
  a

Dry Run Walkthrough

Input: string: "banana"

Goal: Find the longest substring that reads the same forwards and backwards

Step 1: Check palindrome centered at index 0 (single center 'b')

"b" is palindrome, length 1

Why: Every single letter is a palindrome of length 1

Step 2: Check palindrome centered between index 0 and 1 (between 'b' and 'a')

No palindrome longer than 0 here

Why: Even length palindrome check between two characters

Step 3: Check palindrome centered at index 1 (single center 'a')

"a" is palindrome, length 1

Why: Single letter palindrome

Step 4: Check palindrome centered between index 1 and 2 (between 'a' and 'n')

No palindrome longer than 0 here

Why: No even length palindrome here

Step 5: Check palindrome centered at index 2 (single center 'n')

"n" is palindrome, length 1

Why: Single letter palindrome

Step 6: Check palindrome centered between index 2 and 3 (between 'n' and 'a')

No palindrome longer than 0 here

Why: No even length palindrome here

Step 7: Check palindrome centered at index 3 (single center 'a') and expand outwards

"anana" is palindrome, length 5

Why: Expand left and right to find palindrome

Step 8: Check palindrome centered between index 3 and 4 (between 'a' and 'n')

No palindrome longer than 0 here

Why: No even length palindrome here

Step 9: Check palindrome centered at index 4 (single center 'n') and expand outwards

"n" is palindrome, length 1

Why: Single letter palindrome

Step 10: Check palindrome centered between index 4 and 5 (between 'n' and 'a')

No palindrome longer than 0 here

Why: No even length palindrome here

Step 11: Check palindrome centered at index 5 (single center 'a') and expand outwards

"a" is palindrome, length 1

Why: Check last center

Result:

"anana" is the longest palindromic substring
ASCII: a -> n -> a -> n -> a

Annotated Code

DSA C

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

// Function to expand around center and return length of palindrome
int expandAroundCenter(const char *s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && s[R] != '\0' && s[L] == s[R]) {
        L--;
        R++;
    }
    return R - L - 1; // length of palindrome
}

// Function to find longest palindromic substring
void longestPalindrome(const char *s) {
    int start = 0, maxLen = 0;
    int len = (int)strlen(s);
    for (int i = 0; i < len; i++) {
        int len1 = expandAroundCenter(s, i, i);       // odd length palindrome
        int len2 = expandAroundCenter(s, i, i + 1);   // even length palindrome
        int currLen = (len1 > len2) ? len1 : len2;
        if (currLen > maxLen) {
            maxLen = currLen;
            start = i - (currLen - 1) / 2;
        }
    }
    printf("Longest palindromic substring: ");
    for (int i = start; i < start + maxLen; i++) {
        printf("%c", s[i]);
    }
    printf("\n");
}

int main() {
    const char *input = "banana";
    longestPalindrome(input);
    return 0;
}

while (L >= 0 && s[R] != '\0' && s[L] == s[R]) { L--; R++; }

expand left and right pointers while characters match to find palindrome length

int len1 = expandAroundCenter(s, i, i);

check odd length palindrome centered at i

int len2 = expandAroundCenter(s, i, i + 1);

check even length palindrome centered between i and i+1

if (currLen > maxLen) { maxLen = currLen; start = i - (currLen - 1) / 2; }

update longest palindrome start and length if current is longer

for (int i = start; i < start + maxLen; i++) { printf("%c", s[i]); }

print the longest palindromic substring found

Output

Longest palindromic substring: anana

Complexity Analysis

Time: O(n^2) because for each character we expand outwards which can take up to n steps

Space: O(1) because we only use a few variables and no extra data structures proportional to input size

vs Alternative: Compared to dynamic programming O(n^2) with O(n^2) space, this approach uses less memory and is simpler

Edge Cases

empty string

prints empty substring without error

DSA C

int len = (int)strlen(s); for (int i = 0; i < len; i++) { ... }

string with all identical characters, e.g. "aaaa"

returns the entire string as longest palindrome

DSA C

while (L >= 0 && s[R] != '\0' && s[L] == s[R]) { L--; R++; }

string with no palindrome longer than 1, e.g. "abc"

returns any single character as longest palindrome

DSA C

int len1 = expandAroundCenter(s, i, i);

When to Use This Pattern

When asked to find the longest substring that reads the same forwards and backwards, use the expand around center pattern because it efficiently checks palindromes by growing from each center.

Common Mistakes

Mistake: Only checking odd length palindromes and missing even length ones
Fix: Check both odd (center at one character) and even (center between two characters) palindromes

Mistake: Not updating start index correctly when a longer palindrome is found
Fix: Calculate start as i - (currLen - 1) / 2 to get correct substring start

Summary

Finds the longest substring that reads the same forwards and backwards in a given string.

Use when you need to identify the largest palindrome inside a string efficiently.

The key insight is to expand around each character (and between characters) to find palindromes without checking all substrings.