5. Longest Palindromic Substring

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.

---

Solution:

This solution is currently at 948 ms for time and 13.7 mb for space (i.e. beats 83% of run and 92.90% of space among the submissions) as of 07/23/2020. I think I will just stick with this for my interview. I have tried to write good comments. Let me know if you couldn’t understand any part of it.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        result = ""
        
        for i in range(len(s)):
            # this is for odd length palindrome
            word1 = self.checkPalindrome(s, i, i)
            # this is for even length palindrome
            word2 = self.checkPalindrome(s, i, i+1)
            
            #word1 will be max length word from word1 and word2
            word1 = word1 if len(word1) >= len(word2) else word2 
            
            # compare word1 with our result
            result = word1 if len(word1) >= len(result) else result
            
        return result
    
    def checkPalindrome(self, s, lo, hi):
        # expand as long as 'lo' can grow to the left
        # and 'hi' and grow to the right and chracters at those index match
        while lo>=0 and hi<len(s) and s[lo]==s[hi]:
            lo -= 1
            hi += 1
        
        # return the slice from original string that starts from our last matched index of lo and hi. We don't increament hi because python slice goes up to ending index-1
        return s[lo+1:hi]

Python dynamic programming solution. No optimizations.

class Solution:
    def longestPalindrome(self, string):
        """ Dynamic programming algorithm. Based on idea that current
        substring(i, j) is a palindrome if substring(i + 1, j - 1) is
        a palindrome and Si == Sj, i.e. In other words, if we already know that
        current substring is a palindrome we need to add equal characters on both
        sides to make a longer palindrome.

        Time complexity: O(n ^ 2). Space complexity: O(n ^ 2), where
        n is the length of the string.
        """
        # initialize 2-D table for storing results
        n = len(string)
        results = [[False] * n for i in range(n)]
        x, y = 0, 0  # start, end of longest palindromic substring so far

        # every 1-letter substring is a palindrome
        for i in range(n):
            results[i][i] = True

        # 2-letter substring(i, j) is a palindrome if string[i] == string[j]
        for i in range(n - 1):
            if string[i] == string[i + 1]:
                results[i][i + 1] = True
                # change longest palindrome to the 1st 2-letter palindrome
                if not x and not y:
                    x, y = i, i + 1

        # results[i][j] = True if results[i + 1][j - 1] == True
        # and string[i] == string[j]
        for k in range(2, n):
            for i in range(n - 2):
                j = i + k
                # break the loop if it exceeds the boundaries of the matrix
                if j == n:
                    break
                # check if current substring is a palindrome
                if results[i + 1][j - 1] and string[i] == string[j]:
                    results[i][j] = True
                    # len(substring(i, j)) > len(substring(x, y))
                    # this way we always choose 1st longest palindrome
                    if j - i > y - x:
                        x, y = i, j

        return string[x:y + 1]