Longest Palindromic Substring

Patrick Leaton
Published: March 17, 2021, 1:12 a.m.
Problem Description

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters (lower-case and/or upper-case),

 

The description was taken from https://leetcode.com/problems/longest-palindromic-substring/. 

Problem Solution

#O(N^2) Time, O(1) Space
class Solution:
    def longestPalindrome(self, s: str) -> str:
        def helper(left:int, right:int) -> str:
            while left >= 0 and right < len(s):
                if s[left] == s[right]:
                    left -= 1
                    right += 1
                else:
                    break
            return s[left+1:right]
       
        result = ""
        for i in range(0, len(s)):
            current = helper(i, i)
            if len(current) > len(result):
                result = current
            current = helper(i, i+1)
            if len(current) > len(result):
                result = current
        return result

Problem Explanation

We are looking for the longest substring that is a palindrome.

Typically when we are trying to validate a palindrome, we would have two pointers moving inward and would return when they met each other or encountered a mismatch in elements.  However, we could instead move outward with two pointers so that we can test each index as the center of the longest palindromic subsequence. 

We can solve this problem by traversing the string, passing the indices to a helper function that checks for palindromes by moving the pointers inward-out.  Each iteration will allow us to try a different center for a longer palindromic substring and we will return the longest one we were able to find.

We will start by creating the palindrome checking helper function that takes a left pointer and a right pointer that it will try as the center for a palindrome.

        def helper(left:int, right:int) -> str:

 

While the left and right pointers haven't gone out of bounds in the string, we will check for matches of characters in the string.

            while left >= 0 and right < len(s):

 

If there is a match, we will move the pointers outward.  Otherwise, we will break from the loop.

                if s[left] == s[right]:
                    left -= 1
                    right += 1
                else:
                    break

 

After we are out of the loop we will return the portion of the string between the left and right pointers.

If we are out of the loop then that means one of the pointers is out of bounds or was a mismatched character.  With this being said, we don't want to include the current elements the pointers are at in the string slice because they are either out of bounds or not matching.  We will return one index to the right of the left pointer, and since the ending index is not included in Python's string slicing, we just need to return the right pointer index within the slice.

            return s[left+1:right]

Now we can move back to our given function.

Let's initialize our empty string and begin traversing our input string.

        result = ""
        for i in range(0, len(s)):

 

We can create a temporary string by passing our current index into the helper function.

In cases where the palindrome we are looking for is odd like "aba" in "abaad", the middle of the palindrome that we will need to match would just be one character.  For this case, we will pass our current index twice.

            current = helper(i, i)

 

If the length of the temporary string is greater than our current maximum result, we will set the new result to be the temporary string.

            if len(current) > len(result):
                result = current

 

We will then create a new temporary string again by passing our current iteration's index and the next index to the helper function.

In cases where the palindrome we are looking for is even like "abba" in "abbaad", the middle of the palindrome that we will need to match would be two characters.  For this case, we will need to pass two neighboring indices.

            current = helper(i, i+1)

 

Same as last time, if the temporary value that was returned is greater than our current maximum result, we will set the new result to be the temporary string.

            if len(current) > len(result):
                result = current

 

Once we have traversed our input string and tested all possible palindromes through our helper function, we will return the result.

        return result