Longest Repeating Subsequence

'''
Given string str, find the length of the longest repeating subsequence such that it can be found twice in the given string.

The two identified subsequences A and B can use the same ith character from string str if and only if that ith character has different indices in A and B. For example, A = "xax" and B = "xax" then the index of first "x" must be different in the original string for A and B.
'''
class Solution:
    def LongestRepeatingSubsequence(self, s):
        dp={}
        n=len(s)
        def lrs(i,j):
            #print((i,j))
            if (i,j) in dp:return dp[(i,j)]
            if i==n or j==n:return 0
            ans=None
            if s[i]==s[j] and i!=j:
                ans=1+lrs(i+1,j+1)
            else:
                ans=max(lrs(i,j+1),lrs(i+1,j))
            dp[(i,j)]=ans
            return ans
        return lrs(0,0)