longest palindrome substring python Archives

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.

“ABBC” → “BB”
“ABCCBBBA” → “BCCB”
“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.

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.

Summary of Finding the Longest Palindrome in a String with Python

In this post we learned about palindromes and looked at how to get the longest palindrome in a string. We created a dynamic programming solution to getting the longest palindromic substring. Then we tested six different strings to get an idea of how the solution worked.

What is a Palindrome?

Examples of the Longest Palindrome in a String

Finding the Longest Palindromic Substring in Python

Note About Variable Names

Summary of Finding the Longest Palindrome in a String with Python

Further Reading

Share this: