Python Program to Find Longest Palindromic Substring

You can find the longest palindromic substring in Python by expanding around each character using expand_around_center and tracking the longest palindrome found, as in def longest_palindrome(s): ....

Examples

Inputbabad

Outputbab

Inputcbbd

Outputbb

Inputa

Outputa

How to Think About It

To find the longest palindromic substring, check each character as a center and expand outwards while the characters on both sides match. Keep track of the longest palindrome found during this process.

Algorithm

1

Start with an empty longest palindrome string.

2

For each character in the string, expand around it to find odd-length palindromes.

3

Also expand around the gap between this character and the next for even-length palindromes.

4

Update the longest palindrome if a longer one is found.

5

Return the longest palindrome after checking all centers.

Code

python

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

    longest = ""
    for i in range(len(s)):
        odd = expand_around_center(i, i)
        even = expand_around_center(i, i+1)
        longest = max(longest, odd, even, key=len)
    return longest

print(longest_palindrome("babad"))

Output

bab

Dry Run

Let's trace the input 'babad' through the code

1

Start with i=0

Expand around center at index 0 (odd): 'b'; even: '' (no match)

2

i=1

Expand odd around index 1: 'aba'; even around 1 and 2: ''

3

i=2

Expand odd around index 2: 'bab'; even around 2 and 3: ''

4

i=3

Expand odd around index 3: 'a'; even around 3 and 4: ''

5

i=4

Expand odd around index 4: 'd'; even around 4 and 5: ''

6

Longest palindrome found

'bab' (or 'aba')

i	Odd Palindrome	Even Palindrome	Longest So Far
0	b		b
1	aba		aba
2	bab		bab
3	a		bab
4	d		bab

Why This Works

Step 1: Expand Around Center

The function expand_around_center checks characters on both sides of a center to find palindromes by moving outwards while characters match.

Step 2: Check Odd and Even Palindromes

We check two cases: one where the palindrome length is odd (single center) and one where it is even (center between two characters).

Step 3: Track Longest Palindrome

After each expansion, we compare the found palindrome with the longest one so far and update if longer.

Alternative Approaches

Dynamic Programming

python

def longest_palindrome_dp(s):
    n = len(s)
    dp = [[False]*n for _ in range(n)]
    start = 0
    max_len = 1
    for i in range(n):
        dp[i][i] = True
    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2 or dp[i+1][j-1]:
                    dp[i][j] = True
                    if length > max_len:
                        start = i
                        max_len = length
    return s[start:start+max_len]

print(longest_palindrome_dp("babad"))

This method uses a table to remember palindromes but uses more memory and is slower for large strings.

Manacher's Algorithm

python

def longest_palindrome_manacher(s):
    t = '#'.join('^{}$'.format(s))
    n = len(t)
    p = [0]*n
    center = right = 0
    for i in range(1, n-1):
        mirror = 2*center - i
        if i < right:
            p[i] = min(right - i, p[mirror])
        while t[i + (1 + p[i])] == t[i - (1 + p[i])]:
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]
    max_len, center_index = max((n, i) for i, n in enumerate(p))
    start = (center_index - max_len)//2
    return s[start:start + max_len]

print(longest_palindrome_manacher("babad"))

This is the fastest method with linear time but is more complex to understand and implement.

Complexity: O(n^2) time, O(1) space

Time Complexity

The main approach checks each character and expands around it, which can take up to O(n) for each of the n characters, resulting in O(n^2).

Space Complexity

Only a few variables are used to track indices and substrings, so space is O(1) besides input and output.

Which Approach is Fastest?

Manacher's algorithm runs in O(n) time but is complex; the expand-around-center method is simpler and efficient enough for most uses.

Approach	Time	Space	Best For
Expand Around Center	O(n^2)	O(1)	Simple and efficient for most cases
Dynamic Programming	O(n^2)	O(n^2)	When you want to remember all palindrome substrings
Manacher's Algorithm	O(n)	O(n)	Fastest for very long strings but complex