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

• https://www.youtube.com/watch?v=UflHuQj6MVA
• https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/
• https://leetcode.com/problems/longest-palindromic-substring/

Written with StackEdit.