Longest Palindromic substring

'''
M-1: Brute Force
We should traverse all the substring for(i->n)-> for (j=i+1->n) and check all the substring by reversing that if matching, store the max size substring. two loops-> n*n and one loop for checking so Time Complexity= N^3

M-2:
We will still go to all the subtring but can we do two string comparison optimally? so suppose you are at i and j indices of string and you want to check substring from i->j is a palindrome or not?, so if ith and jth character matches then you will need to check is i-1th and j+1th character matches or not, if yes then we will do again in deep on shorter string until it doesn't cross the j and if it croseed, means all were mathching but if ith and jth  character doesn't match at any point, it means it is simply str[i->j] is not the palindrome.

so we will use DP where rows are the starting indices and columns are the ending indices so dp dimension=N*N where dp table will contain eg dp[i][j]=True/False where True means str[i->j] substring is palindrome or not
we will check if s[i]==s[j] if yes->go deeper on s[i-1],s[j-1] else return False and keep updating the dp table before returning.

we will call the function for all the substring(2 for loops) and if function returns true, you can compare the ans lenght and store the palindrom substring.

Some points to remeber:
1.initially the answer will be having the first char because answer can be minimum as 1 char because single char will always be palindrome
'''
def fun(s,i,j,dp):
    if i>=j:
        return True
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]!=s[j]:
        return False
    dp[i][j]= fun(s,i+1,j-1,dp)
    return dp[i][j]
class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp=[[-1]*len(s) for _ in range(len(s))]
        ans=1
        str=s[0]
        for i in range(len(s)):
            for j in range(i+1,len(s)):
                if fun(s,i,j,dp)==True:
                    dp[i][j]=True
                    if ans<j-i+1:
                        str=s[i:j+1]
                        ans=max(ans,j-i+1)
        return str