The set of good strings is defined as follows:
- The string "()" is a good string.
- If S is a good string, each string of the form "(SS...S)" is a good string. That is, if you take any good string, concatenate an arbitrary number of its copies, and then surround the result in parentheses, you will produce another good string.
- Nothing else is a good string.
A subsequence of a string X is any string that can be obtained from X by erasing zero or more of its characters.
You are given a String s.
Each character of s is either '(' or ')'.
Let G be the set of all distinct subsequences of s that are good strings.
Note that G contains each good subsequence only once, even if it can be produced in multiple ways.
For example, for s="(()())" the set G contains the strings "()", "(())", and "(()())".
You are also given an int k.
If there are fewer than k strings in G, return the empty string.
Otherwise, return the k-th lexicographically smallest string in G, counting from 1.
|