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.

Practice

1. What is the main goal of the Longest Palindromic Substring problem?

easy

A. Count the total number of palindromic substrings

B. Reverse the string and compare with original

C. Check if the entire string is a palindrome

D. Find the longest substring that reads the same forwards and backwards

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the longest continuous part of the string that reads the same forwards and backwards.

2. Step 2: Differentiate from related problems

   Counting palindromic substrings or checking the whole string is different from finding the longest palindromic substring.

3. Final Answer:

   Find the longest substring that reads the same forwards and backwards -> Option D

4. Quick Check:

   Longest palindromic substring = Find longest palindrome [OK]

Hint: Longest palindrome means longest continuous mirrored substring [OK]

Common Mistakes:

• Confusing substring with subsequence
• Counting all palindromes instead of longest
• Checking whole string palindrome only

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

easy

A. start, max_len = 0, 1

B. start = max_len = None

C. start, max_len = 1, 0

D. start = max_len = 0

Solution

1. Step 1: Understand variable roles

   We need to track the start index and maximum length of the palindrome found. Starting with 0 and 1 is common because a single character is a palindrome.

2. Step 2: Check initialization correctness

   start, max_len = 0, 1 sets start=0 and max_len=1, which is correct. start, max_len = 1, 0 reverses values incorrectly. Options A, B, and C do not set max_len properly.

3. Final Answer:

   start, max_len = 0, 1 -> Option A

4. Quick Check:

   Initialize start=0 and max_len=1 for single char palindrome [OK]

Hint: Start at 0, max length at least 1 for single char palindrome [OK]

Common Mistakes:

• Setting max_len to 0 initially
• Using None instead of integers
• Swapping start and max_len values

3. What will be the output of the following code snippet?

def expand_around_center(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1

s = "babad"
length = expand_around_center(s, 1, 1)
print(length)

medium

A. 1

B. 5

C. 3

D. 0

Solution

1. Step 1: Understand the function behavior

   The function expands around the center indices (left and right) while characters match, then returns the length of the palindrome found.

2. Step 2: Trace the expansion for s='babad' at center (1,1)

   Center at index 1 ('a'). Expand left=1, right=1: 'a'=='a' true, expand to left=0, right=2: 'b'=='b' true, expand to left=-1 (stop). Length = right - left - 1 = 3 - (-1) - 1 = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Expand around center returns palindrome length 3 [OK]

Hint: Expand while chars match, length = right - left - 1 [OK]

Common Mistakes:

• Not subtracting 1 in length calculation
• Confusing indices after expansion
• Assuming length equals right - left

4. Identify the error in the following code snippet for finding the longest palindromic substring:

def longest_palindrome(s):
    start, max_len = 0, 1
    for i in range(len(s)):
        len1 = expand_around_center(s, i, i)
        len2 = expand_around_center(s, i, i+1)
        length = max(len1, len2)
        if length > max_len:
            start = i - length // 2
            max_len = length
    return s[start:start+max_len]

medium

A. The loop should run till len(s)-1 to avoid index error

B. The start index calculation is incorrect for even length palindromes

C. max_len should be initialized to 0 instead of 1

D. expand_around_center function is missing

Solution

1. Step 1: Analyze start index update logic

   For even length palindromes, start index calculation differs because center is between two characters. Using i - length // 2 works for odd length but not always for even length.

2. Step 2: Identify correct start calculation

   For even length, start should be i - (length // 2) + 1 to correctly locate the palindrome start.

3. Final Answer:

   The start index calculation is incorrect for even length palindromes -> Option B

4. Quick Check:

   Start index must adjust differently for even palindromes [OK]

Hint: Adjust start index differently for even-length palindromes [OK]

Common Mistakes:

• Using same start formula for odd and even palindromes
• Ignoring even length palindrome cases
• Not updating max_len properly

5. Given the string "forgeeksskeegfor", which substring is the longest palindromic substring?

hard

A. "geeksskeeg"

B. "forgeeksskeegfor"

C. "geeksskeegf"

D. "eksskeeg"

Solution

1. Step 1: Identify palindromic substrings in the string

   Check substrings that read the same forwards and backwards. "geeksskeeg" is a palindrome of length 10 inside the string.

2. Step 2: Compare lengths of candidate substrings

   "forgeeksskeegfor" is not a palindrome as a whole. "geeksskeegf" and "eksskeeg" are shorter palindromes.

3. Final Answer:

   "geeksskeeg" -> Option A

4. Quick Check:

   Longest palindrome in "forgeeksskeegfor" is "geeksskeeg" [OK]

Hint: Look for longest mirrored substring inside the string [OK]

Common Mistakes:

• Assuming whole string is palindrome
• Choosing substring with extra characters
• Ignoring palindrome length