Table of Contents

## Coding Challenge

š¬ **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 `'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:

š§© **Exercise**: Implement this idea in Python code and send it to me!

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.