Longest Palindromic Substring in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of longest palindromic substring length

What is the output of the following code snippet that finds the length of the longest palindromic substring in the given string?

DSA Python

def longest_palindrome_length(s):
    max_len = 1
    for i in range(len(s)):
        # Odd length palindrome
        l, r = i, i
        while l >= 0 and r < len(s) and s[l] == s[r]:
            max_len = max(max_len, r - l + 1)
            l -= 1
            r += 1
        # Even length palindrome
        l, r = i, i + 1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            max_len = max(max_len, r - l + 1)
            l -= 1
            r += 1
    return max_len

print(longest_palindrome_length("babad"))

A 3

B 2

C 4

D 5

💡 Hint

Check palindromes centered at each character and between characters.

The longest palindromic substring in "babad" is either "bab" or "aba", both length 3.

🧠 Conceptual

intermediate

Understanding palindrome expansion technique

Why does the algorithm check palindromes by expanding around each character and also between characters?

A To skip checking substrings that are not palindromes

B To handle only odd length palindromes

C To optimize time complexity to O(n)

D To find both odd and even length palindromes

💡 Hint

Think about palindrome lengths and their centers.

Odd length palindromes have a single center character, even length palindromes have two center characters. Checking both ensures all palindromes are found.

❓ Predict Output

advanced

Output of longest palindromic substring

What is the output of this code that returns the longest palindromic substring itself?

DSA Python

def longest_palindrome_substring(s):
    start, max_len = 0, 1
    for i in range(len(s)):
        # Odd length
        l, r = i, i
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if (r - l + 1) > max_len:
                start = l
                max_len = r - l + 1
            l -= 1
            r += 1
        # Even length
        l, r = i, i + 1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if (r - l + 1) > max_len:
                start = l
                max_len = r - l + 1
            l -= 1
            r += 1
    return s[start:start+max_len]

print(longest_palindrome_substring("cbbd"))

A "bb"

B "cbbd"

C "b"

D "c"

💡 Hint

Look for the longest substring that reads the same forwards and backwards.

The longest palindromic substring in "cbbd" is "bb".

🔧 Debug

advanced

Identify the error in palindrome substring code

What error will this code produce when run?

DSA Python

def longest_palindrome_substring(s):
    start, max_len = 0, 1
    for i in range(len(s)):
        l, r = i, i
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if r - l + 1 > max_len:
                start = l
                max_len = r - l + 1
            l -= 1
            r += 1
        l, r = i, i + 1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if r - l + 1 > max_len:
                start = l
                max_len = r - l + 1
            l -= 1
            r += 1
    return s[start:start+max_len]

print(longest_palindrome_substring("abba"))

A TypeError due to wrong comparison

B IndexError due to out of range

C SyntaxError due to missing colon

D No error, outputs "abba"

💡 Hint

Check the line with the if statement inside the second while loop.

The if statement inside the second while loop is missing a colon at the end, causing a SyntaxError.

🚀 Application

expert

Longest palindromic substring count in multiple strings

Given a list of strings, how many of them have a longest palindromic substring of length at least 3? Strings: ["racecar", "abc", "noon", "xyzzyx", "a"]

DSA Python

def longest_palindrome_length(s):
    max_len = 1
    for i in range(len(s)):
        l, r = i, i
        while l >= 0 and r < len(s) and s[l] == s[r]:
            max_len = max(max_len, r - l + 1)
            l -= 1
            r += 1
        l, r = i, i + 1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            max_len = max(max_len, r - l + 1)
            l -= 1
            r += 1
    return max_len

strings = ["racecar", "abc", "noon", "xyzzyx", "a"]
count = 0
for s in strings:
    if longest_palindrome_length(s) >= 3:
        count += 1
print(count)

A 4

B 3

C 2

D 5

💡 Hint

Check each string's longest palindrome length carefully.

"racecar" (7), "noon" (4), "xyzzyx" (6) have palindromes >= 3. "abc" (1), "a" (1) do not. So count is 3.