## 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.

###### Vishal

A voyager on the journey to technology and art of software development. Pursuing arts, music, photography, and ways to live life on the edge

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