Longest Repeating Subsequence

'''
LCS variation: We have to find the repeating subsequence, means if a is the subsequence of s then b should also exist in the s in the same order where each character's index of a should be different from b's, means one character can go in one subsequence only.
Approach: find LCS with the same string, but if index of nth and mth character matches, don't consider it and rest is pure LCS.
'''
def fun(s1,s2,n,m,dp):
    if n<0 or m<0:
        return 0
    if dp[n][m]!=-1:
        return dp[n][m]
    if s1[n]==s2[m] and n!=m:
        dp[n][m]=1+fun(s1,s2,n-1,m-1,dp)
    else:
        dp[n][m]=max(fun(s1,s2,n-1,m,dp), fun(s1,s2,n,m-1,dp))
    return dp[n][m]


class Solution:
    def LongestRepeatingSubsequence(self, s):
        dp=[[-1]*len(s) for _ in range(len(s))]
        return fun(s,s,len(s)-1,len(s)-1,dp)