Longest Repeating Subsequence

Moderate
0/80
Average time to solve is 15m
37 upvotes
Asked in companies
GoogleExpedia GroupPayPal

Problem statement

You are given a string ‘st’, Your task is to find the length of the longest repeating subsequence such that two subsequences don’t have the same character at the same position.

For Example : 
The given string st = AABCBDC.

subsequence

As you can see there are two repeating longest subsequences “ABC” with the same character but different position. Therefore the required answer is ‘3’ as the length of “ABC” is 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’, where ‘N’ denotes the length of string ‘st’.

The second line of each test case contains a string ‘st’.
Output Format : 
For every test case, print the length of the longest repeating subsequence.

Output for each test case will be printed in a separate line.
Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.

All the characters of the given string ‘st’ are uppercase letters.
Constraints : 
1 <= T <= 50
1 <= N <= 100

Time Limit: 1 sec
Sample Input 1 :
2
5
ABCAB
7
ABCBDCD
Sample Output 1 :
2
3
Explanation of Sample Input 1 :
Test Case 1

Given string ‘st = ABCAB’

subsequence

As you can see longest repeating subsequence is ‘AB’
So the length of ‘AB’ =2.

Test Case 2

Given string ‘st = ABCBDCD’

subsequence 

As you can see longest repeating subsequence is ‘BCD'
Return length of ‘BCD’ = 3.
Sample Input 2 :
2
2
BA
4
BCCB
Sample Output 2 :
0
1
Hint

Try to use the  LCS method.

Approaches (3)
Recursive Approach

The basic idea is the same as the longest common subsequence( LCS), only need to exclude the case when (i==j) because we can’t consider both same characters in both the subsequence.

 

Follow this step-

LRS[i][j] = LRS[i-1][j-1] +1 where ( st[i-1] == st[j-1] and i!=j)

LRS[i][j] = max(LRS[i-1][j], LRS[i][j-1]) where ( st[i-1] != st[j-1)

Consider base case if(i==0 and j==0) then LRS[0][0]=0

 

Algorithm

 

  • LRSHelper( st , i, j), to return longest repeating subsequence
  • if(i==0 or j==0 ), base case
    • Return 0
  • if( st[i-1] == st[j-1] and (i!=j) )
    • Return LRS[i][j] = LRS[i-1][j-1] +1
  • Else
    • Return max(LRS[i-1][j], LRS[i][j-1])
Time Complexity

O(2^N), Where ‘N’ is the size of the given string ‘st’.

 

At every point of the stage, we are calling a recursive function with 2 branches and the depth of a single branch can be ‘N’.

Space Complexity

O(N), Where ‘N’ is the size of the given string ‘st’.

 

We are using a call stack for recursive calls.

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