Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 26 Oct, 2021

Hard

```
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.
```

```
‘(‘ 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.
```

```
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 = ‘)’.
```

```
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’.
```

```
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.
```

```
You don’t need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
1 <= N <= 10^5
1 <= K <= 10^9
S[i] = ‘(‘ or S[i] = ‘)’.
Time Limit : 1 sec
```

- 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”.