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

Question

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

Example 1:

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

Example 2:

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

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Python Solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start = 0
        max_len = 1
        l = len(s)
        
        dp_matrix = [[0 for i in range (l)] for j in range (l)]
        
        # diagonal single characters
        for i in range(l):
            dp_matrix[i][i] = 1
        
        # two characters like ba, ab, ba, ad
        for i in range (l-1):
            if s[i]==s[i+1]:
                dp_matrix[i][i+1] = 1
                max_len = 2
                start = i
        
        # general case for strings of len>=3
        k=3
        while k<=l:
            for i in range(l-k+1):
                j=i+k-1
                if s[i]==s[j] and dp_matrix[i+1][j-1]:
                    dp_matrix[i][j] = 1
                    if k>max_len:
                        max_len = k
                        start = i
            k+=1
        return s[start:start+max_len]