Longest Palindromic Substring

Problem

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

For example:

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

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

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

Thought Process

• Make a boolean matric to see which left to right indices equal a palindrome

• Make a variable maxLength and change this variable if $j-i>maxLength$

Solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[False for j in range(len(s))] for i in range(len(s))]
        
        ans = ''
        
        for i in range(len(s)):
            dp[i][i] = True
            ans = s[i]

        maxL = -1
        for i in range(len(s)-1,-1,-1):
            for j in range(i+1,len(s)):
                if s[i] == s[j]:
                    if j-i == 1 or dp[i+1][j-1] == True:
                        dp[i][j] = True
                        if j-i > maxL:
                            maxL = j-i
                            ans = s[i:j+1]
                            
        return(ans)

#Time: O(n^2)
#Space: O(n^2)