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 in this tutorial.

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

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.

python longest palindromic substring solution printout
python longest palindrome substring solution printout

Note About Variable Names

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.

Further Reading

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang
Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly

Leave a Reply

%d bloggers like this: