# Find Longest Palindrome in a Python String (Easy)

## 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('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.

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: