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.

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