# 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]
``````
Scroll to Top