# Longest Repeating Subsequence

Given string **str**, find the **length of the longest repeating subsequence** such that the two subsequences do not have the same character in the same position, i.e., any **ith** character in the two sub-sequences shouldn't have the same index in its original string.

Let the string be,
Str="includehelpisbest"
Output will be:
Longest repeating sub-sequence length is 3
The longest repeating sub-sequence is:"ies"

The output is given above where the repeating sub-sequences are in two different colours. One more repeating subs-sequence can be,

The problem can be solved in similar way as longest Common subsequence problem, where input to

LCS()would be String str both the case. That isLet's discuss the recursive approach first.

Let,

Now,

Think of the following example,

Say the string is:

x1x2...xlSay,

xi==xjandi≠j(this is the constraint what we discussed above)Then obviously we need to find LCS for the remaining part of string

(x1x2...xi-1, x1x2...xj-1)and then add 1 for this valid character match (repeating character match),Else

Maximum of two case,

xi,x1x2...xi-1and stringx1x2...xj.xl1, x1x2...xiand second string leaving characterxj,x1x2...xj-1Now, we need to recur down to 0. So,

Where base cases are,

If you generate this recursion tree, it will generate many overlapping sub-problems and thus, we need to reduce the re-computing. That's why we need to convert it into dynamic programming where we will store the output of the sub-problems and we will use it to compute bigger sub-problems.

Converting to Dynamic programming:C++ Implementation:Output