0005. Longest Palindromic Substring

Medium | String + DP | 80 ms (99.34%), 13.5 MB (92.93%)

❓ Problem Statement

Source: LeetCode - Longest Palindromic Substring GitHub: Solution / Performance

Given a string s, return the longest palindromic substring in s.

✍🏻 Constraints & Example

Constraints:

• 1 <= s.length <= 1000

• s consist of only digits and English letters.

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: s = "cbbd"
Output: "bb"

Input: s = "a"
Output: "a"

Input: s = "ac"
Output: "a"

💡 Ideas

Whether a string is palindromic depends on the previous two chars from the left and right. Thus, we could adopt dynamic programming with a memo to solve this problem.

A two-dimension array is initialized to store whether s[j:i] is a palindromic string by recording as dp[i][j] = True. Then, we iterate the input string by a nested for loop which range is from i = len(s) and j = i+1.

In each iteration, there are three different conditions to help us check palindrome:

1. if i == j, dp[i][j] = True

2. if i == j + 1, dp[i][j] = s[i] == s[j]

3. else, dp[i][j] = (dp[i-1][j+1] and s[i] == s[j])

Note that condition 3 checks whether the shrunk string s[j+1:i-1] is a palindrome string and whether s[i] == s[j]

🤖 Python3 (DP)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # (base case)
        if len(s) < 2: return s

        # ==================================================
        #  Dynamic Programming                             =
        # ==================================================
        # time  : O(n^2)
        # space : O(n^2)
        
        ret = ''
        
        # dp[i][j] = True mean s[j:i] = Palindrome
        dp = [[None] * len(s) for i in range(len(s))]
        
        for i in range(len(s)):
            for j in range(i+1):
                if i == j: dp[i][j] = True
                elif i == j+1: dp[i][j] = s[i] == s[j]
                else: dp[i][j] = (dp[i-1][j+1] and s[i] == s[j])
                
                if dp[i][j] and i - j + 1 > len(ret): ret = s[j:i+1]
                    
        return ret

🤖 Python3 (non-DP)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # (base case)
        if len(s) < 2: return s
        
        # ==================================================
        #  Expand around Corner                            =
        # ==================================================
        # time  : O(n^2)
        # space : O(1)
        
        self.ret = ''
        self.maxLen = 0
        
        for i in range(len(s)):
            # ODD length (aabbdde -> [a'a'b]bdde, a[a'b'd], ..., aabb[d'd'e])
            self.expand(s, i, i)

            # EVEN length (aabbdde -> [a'a']bbdde, a[a'b']bdde, ..., aabbd[d'e'])
            self.expand(s, i, i + 1)
            
        return self.ret
    
    def expand(self, s: str, l: int, r: int) -> None:
        while l >=0 and r < len(s) and s[l] == s[r]:
            if(r - l + 1) > self.maxLen:
                self.ret = s[l:r+1]
                self.maxLen = len(self.ret)
            l -= 1
            r += 1

🤖 Java