Last Updated: 26 Oct, 2021

# Ninja Subsequence

Hard

## Problem statement

#### An empty sequence is regular :

``````If ‘S’ is a regular sequence, then (S) is also regular.

If ‘A’ and ‘B’ represent two regular sequences, then their concatenation ‘AB’ is also regular.

Therefore, the sequences (), ()() and (())() are regular, while ()(, ) and ))() are non-regular.
``````

#### Now Ninja provides you with a parentheses sequence ‘S’ of length ‘N’ and challenges you to find the longest subsequence of the given sequence which is non-regular. Amongst all such distinct subsequences, output the lexicographically ‘Kth’ amongst them. If the number of distinct subsequences with maximum length is less than ‘K’, please output -1 instead.

##### Note :
``````‘(‘ is considered lexicographically smaller than ‘)’.

Two subsequences are distinct if they differ at least at one of the indexes. E.g. ‘))’ and ‘((‘  are distinct whereas ‘((‘ and ‘((‘ are not.
``````
##### Example :
``````N = 5
S = ()
K = 2

Explanation :

All possible subsequences of the given sequence are : ‘(‘ , ‘)’ and ‘()’.

The non-regular subsequences among these are : ‘(‘ and ‘)’.

Of these the lexicographically ‘2nd’ subsequence is ‘)’.

Hence, final result = ‘)’.
``````
##### Input Format :
``````The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains two integers ‘N’ and ‘K’.

The second line of each test case contains a string ‘S’ of length ‘N’.
``````
##### Output format :
``````For each test case, print a string denoting the lexicographically ‘Kth’ non-regular subsequence of string ‘S’.

Print the output of each test case in a new line.
``````
##### Note :
``````You don’t need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 5
1 <= N <= 10^5
1 <= K <= 10^9
S[i] = ‘(‘ or S[i] = ‘)’.

Time Limit : 1 sec
``````

## Approaches

### 01 Approach

#### Approach : We first find all the subsequences of the sequence ‘S’.There are ‘2^N’ such subsequences.Then we select the set of non-regular subsequences among these of maximum length.Then we sort these subsequences.If the total number of subsequences is < ‘K’, we return -1.Else, we return the ‘Kth’ subsequence among these.Algorithm :

• Initialise a variable ‘ans’ as ‘0’.
• Initialise a variable ‘maxi’ as ‘0’ which stores the length of maximum non-regular subsequence.
• Run a for loop from ‘i = 0’ to ‘i = 2^N-1’ :
• Initialise a set ‘st’.
• Initialise a string ‘tmp’ as empty.
• Run a loop from ‘j=0’ to ‘j=N-1’.
• If the ‘jth’ bit is set in ‘i’ :