Longest Common Substring

'''
Variatin of maximum lenght subsequence:
Here you have to return the maximum lenght of the substring possible between s1 and s2.
we check the nth and mth character and if matches, we add the 1 in answer and then check for n-1th and m-1th char.
if Not matches, then obviously the s1 of length n and s2 of length m have 0 matching from the backwards(as we are checking from backside). so we will populate 0 in dp table.

so as we know,what function returns so we will have to check all the possibilities of strings as function only tells the max len substring from backside mathcing, so in main function we will run on the whole string where fun(s1,s2,i,j) returns the maximum length of the substrings in strings s1 ending at ith char and s2 ending at jth char possible from the backside so we are checking all the substring which also means all the n & m possible.


Base condition:
1)if n<0 or m<0 means atleast one string got over, so there can't be any substring,so return 0.

Time complexity: O(n*m) as there are n*m states.
'''
def fun(s1,s2,n,m,dp): #this tell the max length of substring s1[:n] & s2[:m] and checked from the backside so we will to check for all the sublengths.
    if n<0 or m<0:
        return 0
    if dp[n][m]!=-1:
        return dp[n][m]
    if s1[n]==s2[m]:
        dp[n][m]=1+fun(s1,s2,n-1,m-1,dp)
    else:
        dp[n][m]=0
    return dp[n][m]



class Solution:
    def longCommSubstr(self, s1, s2):
        dp=[[-1]*len(s2) for _ in range(len(s1))]
        ans=0
        for i in range(len(s1)):
            for j in range(len(s2)):
                ans=max(ans,fun(s1,s2,i,j,dp))
        return ans