# Longest Repeated Subsequence Problem

The longest repeated subsequence (LRS) problem is the problem of finding the longest subsequences of a string that occurs at least twice.

The problem differs from problem of finding common substrings. Unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

For example, consider the sequence ATACTCGGA

Length of Longest Repeating Subsequence is 4
Longest Repeating Subsequence is ATCG

A T T C G A
A T T C A

Note that repeated characters holds different index in the input string.

The Longest Repeating Subsequence problem is classic variation of Longest Common Subsequence (LCS) problem. The idea is to find LCS of given string with itself i.e. call LCS(X, X) and excluding the cases when index are same (i = j) as repeated characters holds different index in the input string.

The LRS problem has an optimal substructure. The problem can be recursively defined as –

| 0                                      (if i = 0 or j = 0)
LRS[i][j] = | LRS[i-1][j-1] + 1                      (if X[i-1] = X[j-1] & i!=j)
| max (LRS[i-1][j], LRS[i][j-1])         (if X[i-1] != X[j-1])

Below solution finds the length of longest repeated Subsequence of sequence X recursively by using optimal substructure property of LRS problem.

## C++

Output:

Length of Longest Repeating Subsequence is 4

## Java

Output:

Length of Longest Repeating Subsequence is 4

The worst case time complexity of above solution is O(2n) and auxiliary space used by the program is O(1). The worst case happens when there is no repeated character present in X (i.e. LRS length is 0) and each recursive call will end up in two recursive calls.

The LRS problem also exhibits overlapping subproblems. Let us consider recursion tree for sequence of length 5 having all distinct characters whose LRS length is 0.

As we can see above, the same sub-problems (highlighted in same color) are getting computed again and again. As both optimal substructure and overlapping subproblems properties of dynamic programming are satisfied, we can save subproblem solutions in memory rather than computed again and again. This method is illustrated below –

## C++

Output:

Length of Longest Repeating Subsequence is 4

## Java

Output:

Length of Longest Repeating Subsequence is 4

The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).

Above Memoized version follows the top-down approach, since we first break the problem into subproblems and then calculate and store values. We can also solve this problem in bottom-up manner by calculating the smaller values of LRS(i, j) first and then building larger values from them.

## C++

Output:

Length of Longest Repeating Subsequence is 4

## Java

Output:

Length of Longest Repeating Subsequence is 4

The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2). The space complexity of above solution can be improved to O(n) as calculating LRS of a row of the LRS table requires only the solutions to the current row and the previous row.

How to extend above solution for printing Longest Repeating Subsequence?

The idea is very similar to printing Longest Common Subsequence of two strings. Refer this post for details.

## C++

Output:

The Longest Repeating Subsequence is ATCG

## Java

Output:

The Longest Repeating Subsequence is ATCG

Exercise: Write space optimized code for iterative version.

(2 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
Wandering soul

In your pseudocode when you wrote the recursive formula you use “min” instead o “max” as in your code, I think you should correct this, otherwise, people may get confused as I did for a bit. Also I think you should remove the +1 when X_(i-1) != X_(j-1)

Guest
Dharmender

It doesn’t work for case BABB , output is BB which must be B.

Guest

How? Output is correct only as BABB and BABB