# Technical Interviews: Finding the Longest Palindrome

One of the questions you could be asked if you go through a technical interview for a software engineering role is to find the longest palindrome in a given string. This is a medium easy level interview question and shouldn’t take you longer than 15 to 20 minutes to get.

If you want to stop here and think of a solution before you move on to test yourself to see how well you do, go for it. We’re going to go over the dynamic programming solution to finding the longest palindrome in this tutorial.

In this post we’re going to cover:

• What is a Palindrome?
• Examples of the Longest Palindrome in a String
• Finding the Longest Palindromic Substring in Python
• Note for Variable Names
• Summary of Finding the Longest Palindromic Substring

## What is a Palindrome?

The first thing we want to know for this technical interview question is what a palindrome is. A palindrome is simply a string that reads the same forwards and backwards. Numbers that are palindromes include 6, 121, and 676. Words that are palindromes include racecar, radar, and aibohphobia (the fear of palindromes).

## Examples of the Longest Palindrome in a String

Here are some examples of finding the longest palindromic substring in a string. A substring is simply a contiguous sequence of characters in a string.

1. “ABBC” → “BB”
2. “ABCCBBBA” → “BCCB”
3. “CDAABBBAACD” → “AABBBAAA”

## Finding the Longest Palindromic Substring in Python

Now that we know what a palindrome is and what we’re looking for, let’s dive into the code. Since this is a dynamic programming solution, the first thing we’re going to do is declare our table. Then we’ll set each diagonal value to true because each character is a palindrome with itself. We’ll also set the max length to 1 and the starting index to 0.

Now we’ll loop through every possible length from 2 to the length of the string. Note that we have to send the `range()` function at the length of the string plus 1 because the function does not include the highest number in the range. For each possible length we have to loop through the possible start indices.

The first thing we do inside of the inner loop (checking the start indices) is declare an end index. The end index is equal to the start index plus the length minus 1. If the length is 2, we only need to check the current `_start` and end index to see if they’re equal and set their value to true in the table. We’ll also set the max length to 2 and the new start index to the current `_start` index value. Otherwise, we’ll have to check the value of the current start and end index as well as the value of the index one greater than the current start and one fewer than the current end index. If that value is also true, then we can set the new max length to the current length and the new start index to the current `_start` index.

``````def longestPalindrome(_string):
# create dp table
table = [[False for i in range(len(_string))] for i in range(len(_string))]
# set "diagonals" to true
for i in range(len(_string)):
table[i][i] = True
# max length of the longest palindrome is currently 1
max_length = 1
# starting index is currently 0
start = 0
# double for loop to go through all the lengths starting with 2
for length in range(2,len(_string)+1):
# loop through all possible starting indices
for _start in range(len(_string)-length+1):
# declare end index
end = _start + length - 1
# if we're checking for a length of 2
if length==2:
# we only need to check two values
if _string[_start] == _string[end]:
table[_start][end]=True
max_length = length
_start = start
else:
# we need to check the bookend values and ensure the
# values in the middle are already set to true
if _string[_start] == _string[end] and table[_start+1][end-1]:
table[_start][end]=True
max_length = length
_start = start
return _string[start:start+max_length]

print(longestPalindrome("ABBC"))
print(longestPalindrome("ABCCBBBA"))
print(longestPalindrome("CDAABBBAACD"))
print(longestPalindrome("AAB"))
print(longestPalindrome("ABCDEFG"))
print(longestPalindrome("AABBAA"))``````

Our printout will look like the following image.

We name the inner loop variable `_start` above. This is because we already have a variable named `start` declared outside of the loop. To learn more about variable names, read the article on _ and __ variables in Python.