Last Updated: 26 Oct, 2021
Ninja Subsequence
Hard
Asked in company
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
Approaches
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.
Approach :
- We first notice that the maximum length non-regular subsequences are less in number.
- If the string ‘S’ is itself non-regular, then there exists only 1 non-regular subsequence of maximum length.
- Else, all the subsequences of length ‘N-1’ will be non-regular.
- So, we only need to think about the second case.
- Since, the whole string is regular. So, by removing any character from the string makes it non-regular.
- Next we notice that since we require distinct subsequences, removing adjacent same characters will produce the same subsequences.
- Example : If ‘S’ = (()).
- Removing either the 1st character or the 2nd character will produce the same result : ()).
- So, we only need to remove one of the consecutive same characters from ‘S’.
- Now, we think of some way to remove characters such that we maintain the lexicographic order.
- Since ‘)’ > ‘( lexicographically, we will remove ‘)’ characters first and then ‘(‘ characters.
- Now, we need to decide from where to start removing characters, beginning of the string or the end of it.
- We see greedily that removing ‘)’ characters from beginning and later ‘(‘ characters from the end will produce lexicographically ordered subsequences.
- Example : If ‘Str’ = “abab”, then removing ‘b’ from beginning and then ‘a’ from end will produce sorted subsequences as “aab”, “aba” , “abb” , and “bab”.
- Similar pattern exists from string with parentheses as character.
- At each character which can be removed, we decrement ‘K’.
- When ‘K=0’ , we remove the character and return the remaining string.
- If ‘K>0’ after all removals, we return “-1”.
Algorithm :
- Check if the input string ‘S’ is regular.
- If not :
- If ‘K=1’ return ‘S’, else return “-1”.
- Else :
- Run a loop from ‘i=0’ to ‘i=N-1’ :
- Initialize a variable ‘j’ = ‘i’ :
- Keep incrementing ‘j’ till ‘j<N’ and ‘S[j]’ = ‘S[i]’.
- If ‘S[i]’ = ‘)’ :
- Decrement ‘K’.
- If ‘K=0’ :
- Initialise a string ‘ans’ with substring(0,i) + substring(i+1).
- Return ‘ans’.
- Assign ‘i=j’.
- Run a loop from ‘i=N-1’ to ‘i=0’ :
- Initialize a variable ‘j’ = ‘i’ :
- Keep decrementing ‘j’ till ‘j>=0’ and ‘S[j]’ = ‘S[i]’.
- If ‘S[i]’ = ‘(’ :
- Decrement ‘K’.
- If ‘K=0’ :
- Initialise a string ‘ans’ with substring(0,i) + substring(i+1).
- Return ‘ans’.
- Assign ‘i=j’.
- If we reach here, return “-1”.