Longest Repeating Subsequence

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
13 upvotes
Asked in company
Amazon

Problem statement

Given a string 'STR', you are supposed to return the length of the longest repeating subsequence such that the two subsequences don’t have the same string character at the same position which means that any ith character in the two subsequences shouldn’t have the same index in the original string.

For example : 
In a string “abaacbc”, the length of the longest repeating subsequence is 3 considering the subsequence “abc”. The subsequence “abc” which is present at positions [1,2,5] and [4,6,7] are the longest repeating subsequence in the given string.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line contains a single integer ‘T’ denoting the number of test cases.

Each test case contains a single string “STR” denoting the given string.
Output format : 
For each test case, print the length of the longest repeating subsequence.
Note : 
You do not need to print anything; it has already been taken care of. Just complete the function.
Constraints : 
1 <= T <= 5
1 <= N <= 100

Where ‘T’ is the number of test cases.
'N' is the length of the given string.

Time Limit: 1 sec.
Sample Input 1 :
2
aabb
ab
Sample Output 1 :
2
0
Explanation For Sample Input 1 :
In the first test case, the length of the longest repeating subsequence is 2 considering the subsequence “ab”.
In the second test case, cannot find any longest repeating subsequence in the given string so the result is 0.
Sample Input 2 :
2
abacb
abscabdcabd
Sample Output 2 :
2
6
Explanation For Sample Input 2 :
In the first test case, the length of the longest repeating subsequence is 2 considering the subsequence “ab”.

In the second test case, the length of the longest repeating subsequence is 6 considering the subsequence “abcabd”.
Hint

Find out all the subsequences which have the same characters.

Approaches (4)
Recursive

This problem is a little bit modification of the same problem as LCS (longest common subsequence) where we are provided with two strings. And now to use that same concept in our approach we have to consider both the strings equal like in the case of LCS we will use LCS(STR, STR) because we want to find the longest common subsequence among these strings with just one constraint when both the characters are same, they shouldn’t be on the same index in the two strings.

 

The naive approach will be to create a recursion function that keeps a check whether the characters of the strings at position let’s say i and j are equal (while considering i != j ) then return LRS(STR, i-1, j-1) + 1 and if they are not the same characters return max (LRS(STR, i-1, j), LRS(STR, i, j-1)).

Time Complexity

O(N* (2^N)), where ‘N’ is the length of the given string.

 

A string of length ‘N’ has 2^N-1 different possible subsequences since we do not consider the subsequence with length 0. So the overall time complexity will be O(N* (2^N)).

Space Complexity

O(N), where ‘N’ is the length of the given string.

 

Since, we are using a recursive function to find the length of LRS and in the worst case, there may be N state in the call stack. So the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Longest Repeating Subsequence
Full screen
Console