7

Longest Repeating Subsequence

Difficulty: MEDIUM
Contributed By
Sakshi Bansal
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

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.
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 
Reset Code
Full screen
copy-code
Console