Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. Tags: String
Try It!
Discussion
Video
Solution
Dynamic Programming Solution
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False for j in range(n)] for i in range(n)]
ans = ''
# every string with one char is a palindrome
for i in range(n):
dp[i][i] = True
ans = s[i]
# upper dp
for start in range(n - 1, -1, -1):
for end in range(start + 1, n):
if s[start] == s[end]:
if end - start == 1 or dp[start + 1][end - 1]:
dp[start][end] = True
if end - start + 1 > len(ans):
ans = s[start:end + 1]
return ans
Expand from middle solution
class Solution:
def longestPalindrome(self, s: str) -> str:
max_len = 0
max_str = ''
for i in range(len(s)):
# odd
j = i
k = i
while j >= 0 and k < len(s) and s[j] == s[k]:
if k - j + 1 > max_len:
max_len = k - j + 1
max_str = s[j:k + 1]
j -= 1
k += 1
# even
j = i
k = i + 1
while j >= 0 and k < len(s) and s[j] == s[k]:
if k - j + 1 > max_len:
max_len = k - j + 1
max_str = s[j:k + 1]
j -= 1
k += 1
return max_str