Longest Palindromic Substring in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of longest palindromic substring length

What is the output of this C code that finds the length of the longest palindromic substring in the string "babad"?

DSA C

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

int longestPalindromeLength(char* s) {
    int n = strlen(s);
    int maxLen = 1;
    int start = 0;
    for (int i = 0; i < n; i++) {
        int left = i, right = i;
        while (left >= 0 && right < n && s[left] == s[right]) {
            if (right - left + 1 > maxLen) {
                maxLen = right - left + 1;
                start = left;
            }
            left--;
            right++;
        }
        left = i; right = i + 1;
        while (left >= 0 && right < n && s[left] == s[right]) {
            if (right - left + 1 > maxLen) {
                maxLen = right - left + 1;
                start = left;
            }
            left--;
            right++;
        }
    }
    return maxLen;
}

int main() {
    char s[] = "babad";
    printf("%d\n", longestPalindromeLength(s));
    return 0;
}

A 3

B 2

C 4

D 5

💡 Hint

Check palindromes centered at each character and between characters.

The longest palindromic substrings in "babad" are "bab" and "aba", both length 3.

🧠 Conceptual

intermediate

Understanding palindrome expansion

In the approach to find the longest palindromic substring by expanding around centers, why do we check two centers for each index?

A To check palindromes only at even indices

B To speed up the algorithm by parallel processing

C To handle both odd and even length palindromes

D To avoid checking the first and last characters

💡 Hint

Think about palindrome lengths like 'aba' vs 'abba'.

Odd length palindromes have a single center character, even length palindromes have two center characters.

🔧 Debug

advanced

Identify the error in palindrome substring code

What error will this code produce when run, and why? char* longestPalindrome(char* s) { int n = strlen(s); int maxLen = 1, start = 0; for (int i = 0; i < n; i++) { int left = i, right = i; while (left >= 0 && right < n && s[left] == s[right]) { if (right - left + 1 > maxLen) { maxLen = right - left + 1; start = left; } left--; right++; } } s[start + maxLen] = '\0'; return s + start; } int main() { char s[] = "cbbd"; printf("%s\n", longestPalindrome(s)); return 0; }

A It returns a pointer to a local variable causing undefined behavior

B It modifies the input string and may truncate original data incorrectly

C It prints the entire original string without truncation

D It causes a segmentation fault due to invalid pointer arithmetic

💡 Hint

Look at how the string is modified before returning.

The code inserts a null character inside the original string to truncate it, which changes the input string unexpectedly.

❓ Predict Output

advanced

Output of Manacher's algorithm partial array

Given the input string "abacdfgdcaba", what is the value of the palindrome radius array P at index 5 after running Manacher's algorithm?

DSA C

/* Manacher's algorithm partial snippet */
int P[] = {0,1,0,3,0,1,0,1,0,3,0,1,0};
// Index 5 corresponds to character 'f' in the string
// What is P[5]?

A 1

B 0

C 3

D 2

💡 Hint

P[i] stores the radius of palindrome centered at i including i.

At index 5 ('f'), the palindrome radius is 1 meaning only the character itself is palindrome.

🚀 Application

expert

Longest palindromic substring in a large string

You have a string of length 1,000,000 characters. Which approach is best to find the longest palindromic substring efficiently?

A Brute force checking all substrings (O(n^3))

B Dynamic programming with a 2D table (O(n^2) time and space)

C Expand around centers for each character and pair (O(n^2))

D Manacher's algorithm (O(n) time and space)

💡 Hint

Consider time complexity for very large input.

Manacher's algorithm finds longest palindromic substring in linear time, suitable for large strings.