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]
```