Ninja Subsequence

Hard
0/120
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in company
Codenation

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 = ‘)’.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 2    
(()
4 2
(())
Sample Output 1 :
-1
())
Explanation Of Sample Input 1 :
For test case 1 we have, 

The largest non-regular subsequence is (().

There exists only 1 largest length non-regular subsequence but we need to find the 2nd non-regular subsequence.

So we output -1.

For test case 2 we have, 

The largest non-regular subsequence length is 3 and there are two such unique subsequences. They are (() and ()) respectively in lexicographic order.

We are required to print the ‘2nd’ subsequence.

So we output ()).
Sample Input 2 :
2
2 2
()
3 1
(()
Sample Output 2 :
)
(()
Hint

Find all subsequences of the sequence.

 

Approaches (2)
Brute Force

 

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.

 

Time Complexity

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

We are calculating all possible subsequences and checking if they are regular or not, so the overall time complexity is O( N*2^N ).
 

Space Complexity

O(N)
 

There can be maximum ‘N’ non-regular strings of maximum length.Hence, the overall Space Complexity is O(N).

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