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.
- “ABBC” → “BB”
- “ABCCBBBA” → “BCCB”
- “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
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.
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.
- Kruskal’s Algorithm in Python
- AI Keyword Extraction in Python
- Summing a 2D List in Python
- Long Short Term Memory (LSTM) in Keras and Python
- A Software Engineer’s Guide to the Orchestration Pattern
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.
Make a one-time donation
Make a monthly donation
Make a yearly donation
Choose an amount
Or enter a custom amount
Your contribution is appreciated.
Your contribution is appreciated.
Your contribution is appreciated.DonateDonate monthlyDonate yearly