Given a string
s, return the longest palindromic substring in
Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.
Input: s = "cbbd" Output: "bb"
Input: s = "a" Output: "a"
Input: s = "ac" Output: "a"
1 <= s.length <= 1000
sconsist of only digits and English letters.
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]