💬 Challenge: Given a string. How to find the longest palindrome in the string?
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
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
👉 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
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
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[j] are the same. Set the cell to
True accordingly. Initialize the data structure with diagonal values
(i,i) == True.
Here’s a quick overview of this idea:
While working as a researcher in distributed systems, Dr. Christian Mayer found his love for teaching computer science students.
To help students reach higher levels of Python success, he founded the programming education website Finxter.com. He’s author of the popular programming book Python One-Liners (NoStarch 2020), coauthor of the Coffee Break Python series of self-published books, computer science enthusiast, freelancer, and owner of one of the top 10 largest Python blogs worldwide.
His passions are writing, reading, and coding. But his greatest passion is to serve aspiring coders through Finxter and help them to boost their skills. You can join his free email academy here.