Find Longest Palindrome in a Python String (Easy)

by
3.3/5 - (3 votes)

Coding Challenge

💬 Challenge: Given a string. How to find the longest palindrome in the string?

Python - Find Longest Palindrome in a String Example
Figure: The string 'locoannamadam' contains multiple palindromes. The longest palindrome is 'madam'.

For comprehensibility, allow me to quickly add a definition of the term palindrome:

💡 Definition: A palindrome is a sequence of characters that reads the same backward as forward such as 'madam', 'anna', or '101'.

This article wants to give you a quick and easy solution in Python. First, we’ll solve the easier but important problem of checking if a substring is a palindrome in the first place:

Check If Substring is Palindrome

You can easily check if a substring is a palindrome by using the slicing expression word == word[::-1] that evaluates to True if the word is the same forward and backward, i.e., it is a palindrome.

👉 Recommended Tutorial: Python Palindromes One-Liner

Next, we’ll explore how to find the longest substring in a Python string that is also a Palindrome. You can find our palindrome checker in the code solution (highlighted):

Find Longest Substring That is Palindrome

The brute-force approach to finding the longest palindrome in a string is to iterate over all substrings in a nested for loop. Then check each substring if it is a palindrome using word == word[::-1]. Keep track of the longest palindrome using the len() function in an if condition.

Here’s the full solution:

def find_longest_palindrome(s):
    longest = ''
    n = len(s)
    for i in range(n):
        for j in range(i+1,n+1):
            word = s[i:j]
            if word == word[::-1]:
                if len(word)>len(longest):
                    longest = word          
    return longest


print(find_longest_palindrome('locoannamadam'))
# madam

print(find_longest_palindrome('anna'))
# anna

print(find_longest_palindrome('abc'))
# a

Runtime Complexity

This has cubic runtime complexity, i.e., for a string with length n, we need to check O(n*n) different words. Each word may have up to n characters, thus the palindrome check itself is O(n). Together, this yields runtime complexity of O(n*n*n) = O(n³).

Discussion and Better Solutions

Is this the best we can do?

No! The best we can theoretically do is a linear runtime complexity and linear space complexity called Manacher’s Algorithm. The idea is to choose multiple “palindrome centers” and grow these centers one step at a time by adding characters to the left or the right.

However, you’re not expected to come up with this yourself in a coding interview.

Quadratic Programming Idea

What some interviewers may expect is to come up with a “dynamic programming” idea where you construct a Boolean matrix.

Data Structure: Each cell (i,j) of the Boolean Matrix is True if the string s[i:j] is a Palindrome and False otherwise. The cell that is True and has the highest value for j-i represents the longest Palindrome.

Algorithm: Fill the data structure with Boolean values. You can construct a cell (i,j) from the smaller cells easily by checking if the smaller substring s[i+1:j-1] is a Palindrome and the first and last characters s[i] and s[j] are the same. Set the cell to False or True accordingly. Initialize the data structure with diagonal values (i,i) == True.

Note we do NOT use Python indexing in this description, i.e., the end index of a slice is included.

Here’s a quick overview of this idea:

Source

🧩 Exercise: Implement this idea in Python code and send it to me!