Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Last Updated: 26 Oct, 2021

Ninja Subsequence

Asked in company

Problem statement

Ninja has recently learnt about sequences of parentheses. These are special sequences that contain only the characters '(' and ')'.

Ninja studied regular and non-regular sequences of parentheses too. A regular sequence follows the following definition :

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


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’ :
      • Add ‘S[j]’ to ‘tmp’.
    • Check if the string formed is non-regular :
    • If yes :
      • If ‘maxi’<’tmp.size()’ , update ‘maxi’ to ‘tmp.size()’ and clear set ‘st’.
      • If ‘maxi’ = ‘tmp.size()’ , add ‘tmp’ to ‘st’.
  • If the size of the set ‘st’ < ‘K’ :
  • Return -1.
  • Sort the set of strings by prioritising ‘(‘ before ‘)’.
  • Return the ‘Kth’ string of the set.