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.

Practice

1. What is the main goal when finding the Longest Palindromic Substring in a given string?

easy

A. To find the longest substring with all unique characters

B. To find the longest substring that contains only vowels

C. To find the longest continuous sequence of characters that reads the same backward and forward

D. To find the longest substring that is sorted alphabetically

Solution

1. Step 1: Understand palindrome definition

   A palindrome reads the same backward and forward, like 'madam' or 'racecar'.

2. Step 2: Identify substring requirement

   The substring must be continuous characters in the string, not scattered.

3. Final Answer:

   To find the longest continuous sequence of characters that reads the same backward and forward -> Option C

4. Quick Check:

   Longest palindromic substring = continuous palindrome [OK]

Hint: Look for continuous same backward-forward sequences [OK]

Common Mistakes:

• Confusing substring with subsequence
• Looking for unique characters instead of palindrome
• Ignoring continuity of characters

2. Which of the following C code snippets correctly initializes variables to find the longest palindromic substring length?

easy

A. int maxLength = 0; int start = -1; int len = strlen(s);

B. int maxLength = 1; int start = 0; int len = strlen(s);

C. int maxLength = 1; int start = 0; int len = length(s);

D. int maxLength = 1; int start = 0; int len = s.length;

Solution

1. Step 1: Check correct function for string length in C

   In C, strlen() is used to get string length, not length() or s.length.

2. Step 2: Verify variable initialization

   Longest palindrome length starts at 1 (single char), start index at 0, and length is string length.

3. Final Answer:

   int maxLength = 1; int start = 0; int len = strlen(s); -> Option B

4. Quick Check:

   Use strlen() for string length in C [OK]

Hint: Use strlen() to get string length in C [OK]

Common Mistakes:

• Using length() instead of strlen() in C
• Initializing maxLength to 0 instead of 1
• Using Java or C++ string length syntax in C

3. What will be the output of the following C code snippet that finds the longest palindromic substring length?

char s[] = "babad";
int maxLength = 1, start = 0;
int len = strlen(s);
for (int i = 0; i < len; i++) {
    int low = i - 1;
    int high = i + 1;
    while (high < len && s[high] == s[i])
        high++;
    while (low >= 0 && s[low] == s[i])
        low--;
    while (low >= 0 && high < len && s[low] == s[high]) {
        low--;
        high++;
    }
    int length = high - low - 1;
    if (maxLength < length) {
        maxLength = length;
        start = low + 1;
    }
}
printf("%d", maxLength);

medium

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Understand the palindrome expansion logic

   The code expands around each character to find palindromes, including duplicates and symmetric characters.

2. Step 2: Trace the longest palindrome in "babad"

   Longest palindromic substrings are "bab" or "aba", both length 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Longest palindrome in "babad" = 3 [OK]

Hint: Check palindrome centers and expand outwards [OK]

Common Mistakes:

• Assuming entire string is palindrome
• Counting non-continuous characters
• Ignoring multiple palindrome centers

4. Identify the bug in the following C code snippet intended to find the longest palindromic substring length:

char s[] = "cbbd";
int maxLength = 1, start = 0;
int len = strlen(s);
for (int i = 0; i < len; i++) {
    int low = i - 1;
    int high = i + 1;
    while (low >= 0 && high < len && s[low] == s[high]) {
        low--;
        high++;
    }
    int length = high - low - 1;
    if (maxLength < length) {
        maxLength = length;
        start = low + 1;
    }
}
printf("%d", maxLength);

medium

A. The code does not check for even length palindromes correctly

B. The variable 'start' is not updated properly

C. The initial maxLength should be 0, not 1

D. The loops use wrong comparison operators

Solution

1. Step 1: Analyze palindrome detection logic

   The code expands around a single center character, missing even length palindromes like "bb" in "cbbd".

2. Step 2: Identify missing even length palindrome check

   Even length palindromes require checking centers between characters, which is not done here.

3. Final Answer:

   The code does not check for even length palindromes correctly -> Option A

4. Quick Check:

   Missing even length palindrome check = bug [OK]

Hint: Check centers between characters for even palindromes [OK]

Common Mistakes:

• Only checking odd length palindromes
• Not updating start index correctly
• Wrong initial maxLength value

5. Given the string "forgeeksskeegfor", which approach correctly finds the longest palindromic substring and what is its length? A) Brute force method, length 8 B) Dynamic programming method, length 12 C) Expand around center method, length 12 D) Expand around center method, length 10

hard

A. Brute force method, length 8

B. Dynamic programming method, length 12

C. Expand around center method, length 12

D. Expand around center method, length 10

Solution

1. Step 1: Identify longest palindrome in "forgeeksskeegfor"

   The longest palindromic substring is "geeksskeeg", length 10.

2. Step 2: Check method correctness and length

   Expand around center method can find the longest palindrome correctly. The longest palindrome is "geeksskeeg" (length 10).

3. Step 3: Re-examine options

   Expand around center method, length 10 says expand around center method, length 10 which is correct. Other options have incorrect lengths or methods.

4. Final Answer:

   Expand around center method, length 10 -> Option D

5. Quick Check:

   Longest palindrome "geeksskeeg" length 10 [OK]

Hint: Longest palindrome is "geeksskeeg" length 10 [OK]

Common Mistakes:

• Assuming full string is palindrome
• Confusing length 12 with actual palindrome length
• Mixing method with incorrect length