RepeatedStrings
SRM 702 · 2016-11-02 · by lg5293
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
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
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.
"()))((()())" 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: "()"
"(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())" 64 Returns: "(((((((((((((()()()())(()()()())))))))))))))"
Submissions are judged against all 111 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RepeatedStrings with a public method string findKth(string s, int k) · 111 test cases · 2 s / 256 MB per case