# Longest Palindrome Substring in a String

### DP based solution

``````class Solution(object):
def __init__(self):
self.lookup  = {}

def isPalindrome(self, s, dp, i, k):
j = i + k - 1

if s[i] == s[j] and dp[i + 1][j - 1]:
return True

return False

def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
size = len(s)
if size < 2:
return s

dp = [ [False]*size for c in range(size+1) ]

i = j = 0
longest = 0
startIndex = endIndex = 0

while i < size:
dp[i][i] = True

# Handle the case of two repeated chars ('bb')
j = i + 1
if j < size:
if s[i] == s[j]:
dp[i][j] = True

# Always update the index for result.
startIndex = i
endIndex = j
longest = 2
i += 1

# Start finding substrings longer the 2.
k = 3
while k <= size:
for i in range(0, size - k + 1):
if self.isPalindrome(s, dp, i, k):
dp[i][i+k-1] = True
strLen = k

if strLen > longest:
longest = strLen
startIndex = i
endIndex = i + k - 1
k += 1

return s[startIndex: endIndex + 1]
``````

### Resources

Written with StackEdit.

This site uses Akismet to reduce spam. Learn how your comment data is processed.