Leetcode 5. Longest Palindromic Substring

Problem

Leetcode 5 - Longest Palindromic Substring

Example:

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

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

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

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

Approach

We can solve this problem using Dynamic Programming. The idea is to maintain a 2D DP table where dp[i][j] is True if the substring s[i:j+1] is a palindrome. We iterate over all possible substrings and update the DP table accordingly.

Here is the Python code for the solution:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n <= 1:
            return s
        
        dp = [[False] * n for _ in range(n)]
        start, max_length = 0, 1
        
        # Every single character is a palindrome
        for i in range(n):
            dp[i][i] = True
        
        # Check for substrings of length 2
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start = i
                max_length = 2
        
        # Check for substrings of length 3 or more
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    start = i
                    max_length = length
        
        return s[start:start + max_length]

Time Complexity and Space Complexity

Time Complexity: $O(n^2)$
Space Complexity: $O(n^2)$