RepeatedStrings | Topcoder Archive

Problem Statement

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.

Definition

Class:: RepeatedStrings
Method:: findKth
Parameters:: String, int
Returns:: String
Method signature:: String findKth(String s, int k)
(be sure your method is public)

Constraints

s will have between 1 and 150 characters, inclusive.
Each character in s must be '(' or ')'.
k will be between 1 and 10^9, inclusive.

Examples

```
"()))((()())"
```
```
3
```
```
Returns: "(())"
```
This string has the following distinct good subsequences in sorted order: "((()))", "(()())", "(())", "()". The third one in this list is "(())".
```
"))))))))))))(((((((((("
```
```
1
```
```
Returns: ""
```
This string has no good subsequences.
```
"(())(()(()))"
```
```
1
```
```
Returns: "(((())))"
```
```
"(())))()((())())"
```
```
8
```
```
Returns: "()"
```

"(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())"

Returns: "(((((((((((((()()()())(()()()())))))))))))))"

```
"("
```
```
1000000000
```
```
Returns: ""
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.