How to Find the Longest Palindrome in a String Using Python

This occasionally comes up during coding interviews and is actually quite a decent way to test someone’s aptitude of moving back and forth on a string to determine if and where palindromes exist.

If we simply said: “return a boolean if a string is a palindrome”, then threw a couple tests cases at the function, we would expect the developer to loop through the first half of a string while comparing the second half, if it matched all the way to the central pivot, then “yes, the string is a palindrome”.

However, this is a bit more complex.

The problem statement

“Give a string s, find the longest palindromic substring in s.”

Example1:
Input: “lamar”
Output: “ama”

Example2:
Input: “cbbd”
Output: “bb”

Example3:
Input: “rotator”
Output: “rotator”

There may be multiple ways to achieve this, so coming up with a decent time and space answer is more ideal.

How do we solve this?

We start by creating a variable to remember our palindrome (which we hopefully find).

Then we loop through the input string, followed by a second loop in reverse through the same string.

At this point we check both positions to determine their match and return once we’re done.

def longestPalindrome(s) -> str:
    # Create a string to store our resultant palindrome
    palindrome = ''

    # loop through the input string
    for i in range(len(s)):

        # loop backwards through the input string
        for j in range(len(s), i, -1):

            # Break if out of range
            if len(palindrome) >= j-i:
                break

            # Update variable if matches
            elif s[i:j] == s[i:j][::-1]:
                palindrome = s[i:j]
                break

    return palindrome