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.
Example 1:
Input:
str = "axxzxy"
Output: 2
Explanation:
The given array with indexes looks like
a x x z x y 
0 1 2 3 4 5
The longest subsequence is "xx". 
It appears twice as explained below.
subsequence A
x x
0 1  <-- index of subsequence A
------
1 2  <-- index of str 
subsequence B
x x
0 1  <-- index of subsequence B
------
2 4  <-- index of str 
We are able to use character 'x' 
(at index 2 in str) in both subsequences
as it appears on index 1 in subsequence A 
and index 0 in subsequence B.
Example 2:
Input:
str = "axxxy"
Output: 2
Explanation:
The given array with indexes looks like
a x x x y 
0 1 2 3 4
The longest subsequence is "xx". 
It appears twice as explained below.
subsequence A
x x
0 1  <-- index of subsequence A
------
1 2  <-- index of str 
subsequence B
x x
0 1  <-- index of subsequence B
------
2 3  <-- index of str 
We are able to use character 'x' 
(at index 2 in str) in both subsequences
as it appears on index 1 in subsequence A 
and index 0 in subsequence B.
Your Task:
You don't need to read or print anything. Your task is to complete the LongestRepeatingSubsequence() which takes str as input parameter and returns the length of the longest repeating subsequnece.
Expected Time Complexity: O(n^{2})
Expected Space Complexity: O(n^{2})
Constraints:
1 <= |str| <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

	def LongestRepeatingSubsequence(self, str):

		# Code here

Solutions:
class Solution:

	def LongestRepeatingSubsequence(self, str):
		n = len(str)
		dp = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			new_a = [0]
			for j in range(1, n + 1):
				if str[i - 1] == str[j - 1] and i != j:
					new_a.append(1 + dp[j - 1])
				else:
					new_a.append(max(dp[j], new_a[-1]))
			dp = new_a[:]
		return dp[-1]


class Solution:

	def LongestRepeatingSubsequence(self, str):
		s1 = str
		s2 = str
		m = len(s1)
		n = len(s2)
		dp = [[0 for i in range(n + 1)] for i in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if s1[i - 1] == s2[j - 1] and i != j:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[m][n]


class Solution:

	def LongestRepeatingSubsequence(self, str):
		x = len(str)
		T = [[0 for i in range(x + 1)] for i in range(x + 1)]
		for i in range(x + 1):
			for j in range(x + 1):
				if i == 0 or j == 0:
					T[i][j] = 0
				elif i != j and str[i - 1] == str[j - 1]:
					T[i][j] = 1 + T[i - 1][j - 1]
				else:
					T[i][j] = max(T[i - 1][j], T[i][j - 1])
		return T[x][x]


class Solution:

	def lcs(self, str1, str2):
		lcsMatrix = [[0 for i in range(len(str2) + 1)] for j in range(len(str1) + 1)]
		for x in range(len(str1) + 1):
			for y in range(len(str2) + 1):
				if x == 0 or y == 0:
					lcsMatrix[x][y] = 0
				elif str1[x - 1] == str2[y - 1] and x != y:
					lcsMatrix[x][y] = 1 + lcsMatrix[x - 1][y - 1]
				else:
					lcsMatrix[x][y] = max(lcsMatrix[x - 1][y], lcsMatrix[x][y - 1])
		return lcsMatrix[len(str1)][len(str2)]

	def LongestRepeatingSubsequence(self, str):
		return self.lcs(str, str)


class Solution:

	def LongestRepeatingSubsequence(self, str):
		n = len(str)
		arr = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if j > i:
					if str[i - 1] != str[j - 1]:
						arr[i][j] = max(arr[i - 1][j], arr[i][j - 1])
					else:
						arr[i][j] = 1 + arr[i - 1][j - 1]
		return arr[n - 1][n]


class Solution:

	def LongestRepeatingSubsequence(self, s):
		n = len(s)
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if s[i - 1] == s[j - 1] and i != j:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n][n]


class Solution:

	def lcs(self, s1, s2, x, y):
		t = [[-1 for _ in range(y + 1)] for _ in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[j - 1] and i != j:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i][j - 1], t[i - 1][j])
		return t[x][y]

	def LongestRepeatingSubsequence(self, str):
		x = len(str)
		return self.lcs(str, str, x, x)


class Solution:

	def LongestRepeatingSubsequence(self, s1):
		s2 = s1
		n = len(s1)
		dp = []
		for i in range(len(s1) + 1):
			temp = [0] * (n + 1)
			dp.append(temp)
		for i in range(n):
			for j in range(n):
				if i == 0 or j == 0:
					dp[i][j] = 0
				if s1[i] == s2[j] and i != j:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n - 1][n - 1]


import numpy as np

class Solution:

	def rec_sol(self, str1, str2, x, y):
		if x < 0 or y < 0:
			return 0
		if str1[x] == str2[y]:
			if x != y:
				return self.rec_sol(str1, str2, x - 1, y - 1) + 1
		return max(self.rec_sol(str1, str2, x, y - 1), self.rec_sol(str1, str2, x - 1, y))

	def dp_sol(self, x, y, s1, s2):
		dp = np.array([[0] * (y + 1)] * (x + 1))
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[j - 1] and i != j:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		return dp[x][y]

	def LongestRepeatingSubsequence(self, str):
		len_s = len(str)
		return self.dp_sol(len_s, len_s, str, str)


class Solution:

	def LongestRepeatingSubsequence(self, str):
		n = len(str)
		dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif str[i - 1] == str[j - 1] and i != j:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		return dp[n][n]


class Solution:

	def LongestRepeatingSubsequence(self, string):
		str1 = string
		str2 = string
		n = len(string)
		dp = [[0 for x in range(n + 1)] for y in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if str1[i - 1] == str2[j - 1] and i != j:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		return dp[n][n]


from collections import defaultdict

class Solution:

	def solve(self, i, j, str1, str2):
		if i == len(str) or j == len(str):
			return 0
		if i != j and str1[i] == str2[j]:
			return 1 + self.solve(i + 1, j + 1, str1, str2)
		else:
			return max(self.solve(i + 1, j, str1, str2), self.solve(i, j + 1, str1, str2))

	def solve_memo(self, i, j, str1, str2, F):
		if i == len(str1) or j == len(str1):
			return 0
		if F[i][j] != -1:
			return F[i][j]
		if i != j and str1[i] == str2[j]:
			return 1 + self.solve_memo(i + 1, j + 1, str1, str2, F)
		else:
			F[i][j] = max(self.solve_memo(i + 1, j, str1, str2, F), self.solve_memo(i, j + 1, str1, str2, F))
			return F[i][j]

	def solve_tab(self, str):
		n = len(str)
		F = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		for i in range(n - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				if i != j and str[i] == str[j]:
					F[i][j] = 1 + F[i + 1][j + 1]
				else:
					F[i][j] = max(F[i + 1][j], F[i][j + 1])
		return F[0][0]

	def solve_so(self, str):
		n = len(str)
		curr = [0 for _ in range(n + 1)]
		nxt = [0 for _ in range(n + 1)]
		for i in range(n - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				if i != j and str[i] == str[j]:
					curr[j] = 1 + nxt[j + 1]
				else:
					curr[j] = max(nxt[j], curr[j + 1])
			nxt = curr[:]
		return nxt[0]

	def LongestRepeatingSubsequence(self, str):
		return self.solve_so(str)


class Solution1:

	def LongestRepeatingSubsequence(self, str1):
		n = len(str1)
		dp = [[0] * (n + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					continue
				elif str1[i - 1] == str1[j - 1] and i != j:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n][n]

class Solution:

	def solve(self, i, j, n, str1, dp):
		if i == n or j == n:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if str1[i] == str1[j] and i != j:
			dp[i][j] = 1 + self.solve(i + 1, j + 1, n, str1, dp)
			return dp[i][j]
		else:
			dp[i][j] = max(self.solve(i, j + 1, n, str1, dp), self.solve(i + 1, j, n, str1, dp))
			return dp[i][j]

	def LongestRepeatingSubsequence(self, str1):
		n = len(str1)
		dp = [[-1] * n for _ in range(n)]
		return self.solve(0, 0, len(str1), str1, dp)


class Solution:

	def solve(self, i, j, s1, s2, dp):
		if j >= len(s1) or i >= len(s2):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if s1[i] == s2[j] and i != j:
			dp[i][j] = 1 + self.solve(i + 1, j + 1, s1, s2, dp)
		else:
			dp[i][j] = max(self.solve(i, j + 1, s1, s2, dp), self.solve(i + 1, j, s1, s2, dp))
		return dp[i][j]

	def LongestRepeatingSubsequence(self, str):
		s1 = str
		s2 = s1
		(i, j) = (0, 0)
		dp = [[-1 for i in range(len(s1) + 1)] for j in range(len(s2) + 1)]
		return self.solve(i, j, s1, s2, dp)


class Solution:

	def solve(self, str1, str2, a, b, dp):
		if a == 0 or b == 0:
			return 0
		if dp[a][b] != -1:
			return dp[a][b]
		if str1[a - 1] == str1[b - 1] and a != b:
			dp[a][b] = self.solve(str1, str2, a - 1, b - 1, dp) + 1
		else:
			dp[a][b] = max(self.solve(str1, str2, a - 1, b, dp), self.solve(str1, str2, a, b - 1, dp))
		return dp[a][b]

	def LongestRepeatingSubsequence(self, str):
		n = len(str)
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		if n == 0:
			return 0
		a = self.solve(str, str, n, n, dp)
		return a


class Solution:

	def LongestRepeatingSubsequence(self, str):
		n = len(str)
		stateMap = [[0 for _ in range(n + 1)] for i in range(n + 1)]
		for r in range(1, n + 1):
			for c in range(1, n + 1):
				if str[r - 1] == str[c - 1] and r != c:
					stateMap[r][c] = 1 + stateMap[r - 1][c - 1]
				else:
					stateMap[r][c] = max(stateMap[r - 1][c], stateMap[r][c - 1])
		return stateMap[n][n]


class Solution:

	def LongestRepeatingSubsequence(self, str):
		dp = {}

		def lcs(s1, s2, n, m):
			if n == 0 or m == 0:
				return 0
			elif (n, m) in dp:
				return dp[n, m]
			else:
				if s1[n - 1] == s2[m - 1] and n != m:
					c = 1 + lcs(s1, s2, n - 1, m - 1)
				else:
					c1 = lcs(s1, s2, n - 1, m)
					c2 = lcs(s1, s2, n, m - 1)
					c = max(c1, c2)
				dp[n, m] = c
				return c
		return lcs(str, str, len(str), len(str))


class Solution:

	def LongestRepeatingSubsequence(self, inputString1):
		dynamicArray = [[0 for x in range(len(inputString1) + 1)] for y in range(len(inputString1) + 1)]
		for rows in range(1, len(inputString1) + 1):
			for cols in range(1, len(inputString1) + 1):
				if inputString1[rows - 1] == inputString1[cols - 1] and rows != cols:
					dynamicArray[rows][cols] = 1 + dynamicArray[rows - 1][cols - 1]
				else:
					dynamicArray[rows][cols] = max(dynamicArray[rows][cols - 1], dynamicArray[rows - 1][cols])
		return dynamicArray[-1][-1]


class Solution:

	def LongestRepeatingSubsequence(self, str):
		b = str
		c = str
		dd = []

		def recc(b, c, i, j, arra):
			if i == len(b) or j == len(c):
				return 0
			ans = 0
			if arra[i][j] != -1:
				return arra[i][j]
			if b[i] == c[j] and i != j:
				ans = 1 + recc(b, c, i + 1, j + 1, arra)
			else:
				ans = max(recc(b, c, i + 1, j, arra), recc(b, c, i, j + 1, arra))
			arra[i][j] = ans
			return arra[i][j]
		arra = []
		for k in range(0, len(b)):
			arra1 = []
			for l in range(0, len(c)):
				arra1.append(-1)
			arra.append(arra1)
		ans = recc(b, c, 0, 0, arra)
		return ans


class Solution:

	def LongestRepeatingSubsequence(self, str):
		m = len(str)
		dp = [[0 for _ in range(m + 1)] for _ in range(m + 1)]
		res = 0
		for i in range(1, m + 1):
			for j in range(1, m + 1):
				if str[i - 1] == str[j - 1] and i != j:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]


class Solution:

	def LongestRepeatingSubsequence(self, s):
		(s1, s2) = (s, s)
		(m, n) = (len(s1), len(s2))
		t = [[None] * (n + 1) for i in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
				elif s1[i - 1] == s2[j - 1] and i != j:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i][j - 1], t[i - 1][j])
		return t[m][n]


class Solution:

	def LongestRepeatingSubsequence(self, A):
		B = A
		n = len(A)
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if A[i - 1] == B[j - 1] and i != j:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]


class Solution:

	def LongestRepeatingSubsequence(self, s):
		x = len(s)
		y = len(s)
		s1 = s2 = s
		dp = [[-1] * y for i in range(x)]

		def findlcs(i, j, x, y, s1, s2, flag):
			if i < 0 or i >= x or j < 0 or (j >= y):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			val = 0
			if s1[i] == s2[j] and i != j:
				val = 1 + findlcs(i + 1, j + 1, x, y, s1, s2, 1)
			val = max(val, findlcs(i + 1, j, x, y, s1, s2, 0))
			val = max(val, findlcs(i, j + 1, x, y, s1, s2, 0))
			dp[i][j] = val
			return val
		return findlcs(0, 0, x, y, s1, s2, 0)


class Solution:

	def LongestRepeatingSubsequence(self, str):
		n = len(str)
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]

		def rec(str, i, j):
			if i < 0 or j < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if str[i] == str[j] and i != j:
				dp[i][j] = 1 + rec(str, i - 1, j - 1)
			else:
				dp[i][j] = 0 + max(rec(str, i - 1, j), rec(str, i, j - 1))
			return dp[i][j]
		prev = [0 for i in range(n + 1)]
		curr = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if str[i - 1] == str[j - 1] and i != j:
					curr[j] = 1 + prev[j - 1]
				else:
					curr[j] = 0 + max(prev[j], curr[j - 1])
			prev = curr[:]
		return prev[n]


class Solution:

	def LongestRepeatingSubsequence(self, str):
		n = len(str)
		t = [[0 for _ in range(n + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if str[i - 1] == str[j - 1] and i != j:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return t[-1][-1]


class Solution:

	def fun(self, i1, i2, s1, s2, dp):
		if i1 == 0 or i2 == 0:
			return 0
		if dp[i1][i2] != -1:
			return dp[i1][i2]
		if s1[i1 - 1] == s2[i2 - 1] and i1 != i2:
			dp[i1][i2] = 1 + self.fun(i1 - 1, i2 - 1, s1, s2, dp)
			return dp[i1][i2]
		else:
			dp[i1][i2] = 0 + max(self.fun(i1 - 1, i2, s1, s2, dp), self.fun(i1, i2 - 1, s1, s2, dp))
			return dp[i1][i2]

	def LongestRepeatingSubsequence(self, str):
		s1 = str
		s2 = s1
		n = len(s1)
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i1 in range(1, n + 1):
			for i2 in range(1, n + 1):
				if s1[i1 - 1] == s2[i2 - 1] and i1 != i2:
					dp[i1][i2] = 1 + dp[i1 - 1][i2 - 1]
				else:
					dp[i1][i2] = 0 + max(dp[i1 - 1][i2], dp[i1][i2 - 1])
		return dp[n][n]


class Solution:

	def func(self, X, Y, m, n, t):
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if X[i - 1] == Y[j - 1] and i != j:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return t[m][n]

	def LongestRepeatingSubsequence(self, str):
		m = len(str)
		t = [[0 for i in range(m + 1)] for i in range(m + 1)]
		c = self.func(str, str, m, m, t)
		return c


class Solution:

	def LongestRepeatingSubsequence(self, str):

		def longestRepeatingSubsequence(str1, str2):
			(m, n) = (len(str1), len(str2))
			dp = [[-1 for j in range(n + 1)] for i in range(m + 1)]
			for j in range(n + 1):
				dp[0][j] = 0
			for i in range(1, m + 1):
				dp[i][0] = 0
			for i in range(1, m + 1):
				for j in range(1, n + 1):
					(ch1, ch2) = (str1[i - 1], str2[j - 1])
					if ch1 == ch2 and i != j:
						dp[i][j] = 1 + dp[i - 1][j - 1]
					else:
						dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
			return dp[m][n]
		(s1, s2) = (str, str)
		return longestRepeatingSubsequence(s1, s2)


class Solution:

	def LongestRepeatingSubsequence(self, s):

		def manu(i, j, s):
			if i == len(s) or j == len(s):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if s[i] == s[j] and i != j:
				k = 1 + manu(i + 1, j + 1, s)
			else:
				k = max(manu(i + 1, j, s), manu(i, j + 1, s))
			dp[i][j] = k
			return k
		dp = [[-1 for i in range(len(s))] for i in range(len(s))]
		return manu(0, 0, s)