Longest non regular parentheses sub-sequence
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Chef has recently learnt about sequences of parentheses. These are special sequences that contain only the characters '(' and ')'.
A regular parentheses 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, you need to find the longest subsequence of the given sequence which is non-regular. Amongst all such distinct answers, output the lexicographically Kth amongst them. If the number of distinct subsequences with maximum length is less than K, please output -1 instead.
The first line contains a single integer T, denoting the number of test cases to follow.
Each of the test cases have exactly two lines, the first contains the parentheses sequence and the second contains the value of K.
Output exactly T lines, each containing answer to the corresponding query.
- 1 ≤ T ≤ 10
- 1 ≤ |S| ≤ 105
- 1 ≤ K ≤ 109
5 () 2 (() 1 (() 2 (()) 2 (()) 3
) (() -1 ()) -1
Case 1: Following are the subsequences:
Length Subsequence Regular/Non-Regular 1 ( Non-regular 1 ) Non-regular 2 () Regular
There are two non-regular subsequences of equal length:'(' and ')'.
We are asked for the lexicographically 2nd, so output should be ')'.
Case 2: Following are the subsequences:
Length Subsequence Regular/Non-Regular 1 ( Non-Regular 1 ) Non-Regular 2 (( Non-Regular 2 () Regular 3 (() Non-Regular
In this case, there are non-regular subsequences of lengths 1, 2, and 3. But, as 3 is the maximum among these, we choose, (().
The string is same as Case 2, and we realize that there is only one subsequence of the maximum length 3, thus we must output -1.
We can find that following subsequences have maximum length and are non-regular.
Length Subsequence 3 ()) 3 (()
In lexicographical order, we have following subsequences: [ ((), ()) ]
The query asks for 2nd subsequence, thus the required output is ()).
This is the same sequence as last case, and we know that there are exactly 2 distinct subsequences of maximum length. Thus, answer should be -1.
- A subsequence of a given sequence A is a non-empty sequence obtained by removing zero or more characters from A. It does not need to be contiguous.
- A sequence A is called different from another sequence B, if there exists an integer k, such that 1 ≤ k ≤ N (N is the length of both sequences), and Ak != Bk.
- Consider two different N-length sequences, A and B. Let k be the smallest integer such that A[k] != B[k] and 1 ≤ k ≤ N. If A[k] < B[k], then A is said to be lexicographically smaller than B, and vice-versa.
|Tags||basic-prog, code_master01, cook59, easy-medium, pattern, stack|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.