Python Program to Find Longest Palindromic Substring

A palindromic substring is a sequence of characters that reads the same forward and backward. Finding the longest such substring is a classic problem in programming.

In this tutorial, we will explore multiple approaches ranging from brute force to optimized techniques.

1. Understanding the Problem

Given a string, find the longest substring that is a palindrome.

Input: babad
Output: bab (or aba)

2. Method 1: Brute Force

              
            
Python

          Check all substrings
        
def is_palindrome(s):
    return s == s[::-1]

string = input()
max_str = ""

for i in range(len(string)):
    for j in range(i + 1, len(string) + 1):
        substr = string[i:j]
        if is_palindrome(substr) and len(substr) > len(max_str):
            max_str = substr

print(max_str)

This method checks all substrings and is not efficient for large inputs.

3. Method 2: Expand Around Center

              
            
Python

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

string = input()
longest = ""

for i in range(len(string)):
    odd = expand(string, i, i)
    even = expand(string, i, i + 1)
    
    longest = max(longest, odd, even, key=len)

print(longest)

This method expands around each character and is much more efficient.

4. Method 3: Dynamic Programming

              
            
Python

          DP approach
        
string = input()
n = len(string)
dp = [[False]*n for _ in range(n)]
start = 0
max_len = 1

for i in range(n):
    dp[i][i] = True

for i in range(n-1):
    if string[i] == string[i+1]:
        dp[i][i+1] = True
        start = i
        max_len = 2

for length in range(3, n+1):
    for i in range(n - length + 1):
        j = i + length - 1
        if string[i] == string[j] and dp[i+1][j-1]:
            dp[i][j] = True
            start = i
            max_len = length

print(string[start:start+max_len])

Dynamic programming improves efficiency by storing intermediate results.

5. Method 4: Using Function

              
            
Python

          Reusable function
        
def longest_palindrome(s):
    res = ""
    
    for i in range(len(s)):
        l = r = i
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if (r - l + 1) > len(res):
                res = s[l:r+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) > len(res):
                res = s[l:r+1]
            l -= 1
            r += 1

    return res

print(longest_palindrome("cbbd"))

This method wraps the center expansion logic into a reusable function.

6. Method 5: Return Length Only

              
            
Python

          Return length
        
string = input()
max_len = 0

for i in range(len(string)):
    for j in range(i, len(string)):
        substr = string[i:j+1]
        if substr == substr[::-1]:
            max_len = max(max_len, len(substr))

print(max_len)

This variation returns only the length of the longest palindrome.

7. Algorithm

1. Take input string.

2. Consider each character as center.

3. Expand for odd and even length palindromes.

4. Track longest substring.

5. Return result.

8. Common Mistakes

1. Ignoring even-length palindromes.

2. Incorrect boundary conditions.

3. Using inefficient brute force for large strings.

4. Confusing substring with subsequence.

9. Applications

1. DNA sequence analysis.

2. Text pattern recognition.

3. Data compression.

4. Interview problem solving.

Conclusion

The longest palindromic substring problem is a key interview question that teaches optimization techniques.

Expand around center is the best balance between simplicity and efficiency.