Statistics

Problem Statement for "RepeatedStrings"

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

  1. "()))((()())"

    3

    Returns: "(())"

    This string has the following distinct good subsequences in sorted order: "((()))", "(()())", "(())", "()". The third one in this list is "(())".

  2. "))))))))))))(((((((((("

    1

    Returns: ""

    This string has no good subsequences.

  3. "(())(()(()))"

    1

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

  4. "(())))()((())())"

    8

    Returns: "()"

  5. "(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())"

    64

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

  6. "("

    1000000000

    Returns: ""

  7. "))))))()(()))(((())("

    2

    Returns: "(()())"

  8. "()))))))))))())))))))))())))()))))))))))())))()))))()))))))))()))))())))))()))))))))))"

    6

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

  9. "))((()())(()())()))((()))))))))())()))())()(())()(()()())())))()()()(()())))())()))(()((()())())))()))"

    391

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

  10. ")()))))(()))(()(()())()()))(()((())(()))(()(())((((()(()))(())(())(())(())((()))))()()))))(((()())())(()("

    1293

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

  11. ")))))))))))))))))())))))())))(()))))()())))))))))))))))))())))))())))()))))))))))))))))))))()))))())))()))))))))))()))))))("

    105

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

  12. "))())())))))))(()))))))())()()(())))()"

    1

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

  13. "))(())(())))))))"

    5

    Returns: "()"

  14. "))())))))())))))))()))))))))()))))))(()))))))())))()))()))())))("

    39

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

  15. ")()(((((((()))(((())(()()(())())(((((()((((()"

    75

    Returns: "()"

  16. ")))))(()())(()(()())(())()()))))()()))(()()))))((()))(())))))((((()))()())(()(())()(((("

    226

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

  17. "))))())())))()))))))))))())())))())()))(())())((()()())))))())()"

    58

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

  18. "(()()((((((((((((()((((("

    2

    Returns: "(())"

  19. ")()))(()((())))))(())))((())((((()))())(())))(()))))))((()((()(()(())())()))(()()))(()((()(()()(()))()())()(()())()()())())(()())(())(()("

    697

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

  20. ")))))))))))))))))))))))))))())))))))))))))()))))))))))))))))))))))))))))))))))))))"

    2

    Returns: "()"

  21. "(((((()((()(((())((((((()((())(((((((((((()(()((((((((((((((((((()())((((((()((((((((((((((()((((()(((((((()((((((()(((((((((((((((("

    6

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

  22. "))()((()())(((()((((()))()()((())())))))))))()((())(()))((()))()))())())()((())((()))))))"

    603

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

  23. "()))))))()(()())()()())))))()))(()))(()(((((())))((())(())))(())))(()))))))(()))))))())())))))(()()))()())))))(((("

    842

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

  24. ")))))))))))))))))))))))))()))))))))())))()))))))))(()))))())))))))"

    7

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

  25. ")))()))))((()())(())((()())((((())))))))(()(((()))()()(()()()(()(())()()(((()(())(()())()(()(()()((((((()()((())))(())(()()())))(())("

    3074

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

  26. "))))))())(()((((((()()))())())))()))()(()()(()))(()()()))()"

    29

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

  27. "()))()))))"

    2

    Returns: "()"

  28. "))))((())((()))))()))()()(((()())()((()(((((())()())(()))((()))((()()(()((())()))())((()))()((()))(())()))(()"

    1028

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

  29. "))()(((((((()(()))())()()))())()))((()()(()))(())"

    186

    Returns: "(())"

  30. "))))))))))))))))))))))))))))))))"

    1

    Returns: ""

  31. ")))(())()))())((())(()())))((()))()()(((())((((())(()(((())((((()(()()())))()(())((("

    17

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

  32. "((((()()(()))()(((((((((()()(()((((((((((((()(((((((((()(()((((((((())(())())(()(((()))()(())((((()(((()(("

    41

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

  33. "(((((((("

    1

    Returns: ""

  34. ")()()(())(((()))()))()((((()()()))))))(()))(()))(((())()((()))())))())(()))))(()))(()(()))))(())))((()())))((()()((()(()))(()"

    38

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

  35. "))))(()))((())))()((()(()(())(())(()((()(()))))))())((()()))(())))()())(((()(((())))))(())())()())))()))((())("

    487

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

  36. "((((()((((((((((((((((()(()(((((()((((((()((((((((((((()((((()((()(((((((()((((((((((((()((((((((((((((((((((((((((((()()((((((((((((((((()(((((((((("

    113

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

  37. "()(())))(()(((()()()()(()(()))(())))()))(())())(()))()((((((((()((()(())))())(()()(())()())()()"

    88

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

  38. ")))))))))())))))()))))()))))))))))))())())))))())(()()))))))))))))()))))))()))()())))))))))))())))))))))))(()))))))))"

    30

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

  39. "((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((("

    1

    Returns: ""

  40. ")))))()((()))(()()()(())((((()()())((()))))))()((())())()())))))))))(()(()))((()()()(())))((((()(()()())()))((((()(()())()))()"

    2152

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

  41. "())((((()()(()(())((((((()((()((()((((()((((((((((((((()()))(((()(()(((((((())()()(()()())(((())())(()())(())()(()"

    614

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

  42. "())))))))))))))))))()))))))))))))))))))))))))))()()))())))))))))))))))))))))))))))))))))))))))))))))))))())())))"

    6

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

  43. "((((()(())(())))))))()(()())(())())()))))))(()(())(()()(())()))()()))((()))((()()()"

    964

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

  44. "(()(((())(((()()()(()()()()((((()(((((((((())((((((((())((((((((((((((((((((()()))((()((((((((((((((("

    242

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

  45. ")()))))))())(()())())())))(()()))()()(((()(()))))))(((())))()))(((()())()())()))()())(())())))())"

    14

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

  46. "))())((()((()(())(()()()((()))()())"

    72

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

  47. ")))))))))))))))"

    1

    Returns: ""

  48. "(((((((()(((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((("

    1

    Returns: "(())"

  49. "((())())()(((()(())))))))()))))(())()((()((())))()(())())"

    200

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

  50. ")()())))()))))))()())))(()))()))))())))()))))(()))))))())))())))))))"

    22

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

  51. "(()(()())(()())((((()(((((((())))((((()))(()(()((()(((()()((())(())()))()()(()()((((()())"

    242

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

  52. "()))((()())((((()()((()((()))))((((()))()()()())))(())(((())())(())()))(((())))()(((()())())(())((()((()))())(()())((()))()(((()(()))))())((()(()(()()"

    3868

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

  53. "))())())))())))))))))))))))))()))()))))))()))))())))())))())))()))()()))))))()((())))))))))))))))))))))()()))())())))))))))))))))()))))))))))))))())()"

    357

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

  54. "(()()((())(((()((((((((((())(((())()()(((((((((((()(((()((((())(()(((()(()())((((((((()()))))()(((((()(()()(((((((()((((((())((()(((()(((()(()()(())()"

    1513

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

  55. "((((()(()()))(()())())())((())())(())()(())))()))((()())))()))()))(()))(()()))))()(())))))()(())))))()(()((()()((()()()))()()((((((((()))(())()()))(()"

    2890

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

  56. "))())((()))()()((()))()((()))()()())(((()))())((((()()())()()))((()(((()(()(()()(()())())(((()((()()))(((()())(())()(())(((())((())((())(()))((((())))"

    2101

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

  57. "((()((((((())()))(()))(((())(((()())()()))"

    104

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

  58. "()())(()()()((()()((()(((()()()(((()((("

    19

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

  59. "((((()(((((()()())()(()(()(())(((()(()(()((()((())(((((()(()()(()((()()((((((((((()(()"

    162

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

  60. "())((())())())()((()(()((((((())(()))(()))()((((())))()))(()()()(()((()(((()(((())((())()(((()(()())))()())(()())())((()))((()(((((())()()(()()(((()(("

    482933068

    Returns: ""

  61. "()))()(((())((()((((((())())(((((()(()()(()(()))()))(())()(()(()(()(()))))(()(())(())))()(()(()()())())()()))(()(((()(((()))()())(())(())(())))(((())("

    886536594

    Returns: ""

  62. "()()(()()("

    3

    Returns: "()"

  63. ")))))))))))))))))))))))))())()))))))))))))()))()))())))))))))))))))))))))))))))))))))))))))))))))))))()))))))))))))))()))))))(())))))))))))))))))())"

    34

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

  64. "))(()))))(()((())()(()))((((())()))())))())())(())((()(()))(()))))))))())((())))((((((())))())(((()()(())()))(()(())))()()()"

    710

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

  65. "(()()"

    2

    Returns: "()"

  66. "(((((((((()(((((()(((((((((((((((((((((((())"

    7

    Returns: "()"

  67. ")()))())(()))))())()))())(())((()))))()(()()())(()()(()))()()))())))()(())()(((()()))()))(()()(()(()(((()(()))()()(()))()()((()(((("

    3071

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

  68. ")((())())(()()))())(((((()()))((()()(())(())))()((())))(()())(()((()()))))()()()())()()()))((((((()))))))))()((()())()())(())(()()())(()()((()("

    3364

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

  69. ")()))(())((()(()((())))("

    17

    Returns: "(())"

  70. "))))))))))))))))))))()())))))))))))))))))))))))))))))))))))))))))())))))))(()))))))))))))()))))))))())))))))))))))))))))))))))())))))"

    32

    Returns: "()"

  71. ")(())()((((((())()()()())(())())))))))(()))))))))()(()()())((())(((())()()))()(((()(((((())((()(())())))()))(())(()))(()()((())))(((())))("

    2424

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

  72. "(((((((((((((((()((((((((()()(((((((((((((((((((((((()()(((()((((((()(((((((((((((((((()((((()(((((((((((((((((())()(())(((((((((((((((((((((((("

    63

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

  73. "())()(((((((((()((((())()())(((())())(()(()()))((())(()()((((("

    131

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

  74. ")((()))))()))(()()))))(()()())(((()))())()))(((()(()))()))()))(()()()(((((((()()))((()())))((((()((()())))))))((((())))))((()((()(()(()(()))("

    3968

    Returns: "()"

  75. "((()((((())))(()()(()()(((()((()))))(((((())()(()(())((()((())()()()))(()))))))()))())())()(()(((()()(()()()()))()(("

    2100

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

  76. "))(()(()(()()(())()(((()"

    11

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

  77. ")()()())()())))(())()()(()(()))))(()()()()(())(())(()(()(())()(()(((())))(()())())()))(()()(())()())()())))((()((()((())(()()())))(())(()(("

    5199

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

  78. ")))))))())((()())(((())())(()))))()((()()))())))))()))((()))))())()(()))()(((()((("

    398

    Returns: "()"

  79. "())))))())))(((((()(((((())))(()))))())(()))((()))()((()())())))(())(()(())))))))))())(((()))("

    1126

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

  80. "))(((()()()))))(("

    3

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

  81. "(((((()(((())(((())()(((((((((()((((("

    4

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

  82. "()))())()))))())"

    5

    Returns: "()"

  83. ")))()((()))(()(())())((())(((()(())((((())(((()())(()(()())()))))(((()))))()())))))((((((())))()(((())((((()))()))))(()()"

    1166

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

  84. ")))))))((()())))((())(()(()((((((())(((())))((()(()))(((()(((())(((()()()())(()())()((((()()()(()()(()())(((()"

    106

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

  85. "((((()(((()(()(((()(()()(((((()((((((((()()(((((((((((()(((((((("

    21

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

  86. "))))))((()()(()((((((()((())())((()()())()((())(()()((()((((())(())()((()()()(()(((((((()(())())())()((("

    1624

    Returns: "()"

  87. ")))))))))))))))))))))))))))))))))))))))))"

    1

    Returns: ""

  88. ")(())(())(()(())(()()()))(()(((())))))(()(())))(((()()(((()))(()))(()((()))()))()()))((()())))))"

    865

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

  89. "()(((())(()()()()(())))((())()()((((()((((())(()())(((()((()()())((())))())))(()("

    764

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

  90. "(()(((((((((((((((((((((((((((((((((()(((((((()(((((((((("

    3

    Returns: "()"

  91. "))())))())())((())())))))))(()))))))(()()))()(()())(()))(()(()))((()))()()))))))))()()())))(()()))))(()"

    861

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

  92. "()))((((()())()(((((()(()((())(()))()()(()())()()()))()(())())(()(()(((())))()())()(((()))(()()(((()))((())())())()()())))))()(()(()(()))))((()()()())"

    4818

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

  93. "(()))()((()((()())())(())()(((((((()))()(()))()))()))))))))()(()((((())(((()()()))))))())(()())()))()(((()((())))(()))))(((()))(()())))(()((()()()))))"

    3250

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

  94. "((())()(((((((((()(()(((((())(()((((())())((((((((()((((()(()(((((())((((()((())(((((((((((((()((()(((((((((((((())(((((())(()((()((()(((((()(((((()))"

    1697

    Returns: "()"

  95. ")(()))(())(((())))(((((()())()(()()((((((())(()))())())(())(())))))())))(((())())(()())))))()((()(((((()()))))()()))())())((()()(((()(()()((()(()))))("

    5141

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

  96. "))))))))((()()))))())))())))))()))))(()())()())(()()))())))))))())())(()()()())()()))))())((()))))))))()))))()))))))))())))))())((())()))))))((()))())"

    2097

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

  97. ")))()((()((()))()))()(())((((())()(()()(()))())(()(()(((()()((()))(()()()()))()(()()(()(((()())(((((())()))))()))(()(())()(()()()()((((((()()())))(((("

    6569

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

  98. "()(()())()((()((())(()()()(()())))()())()())(()()(()(()(()()((())))((((())()))())))))))(((((((()))())((((()(()((()(()((())(((()(()()(()()(((()())())()"

    6610

    Returns: "()"

  99. "))))))))))))))))))))))())))))))))))))))))))))())))()))))))))))))))))))))))))))))))))(())))))))))))))))))))))))())))))))))())))))))))))())))())))))))))"

    25

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

  100. "(((()()(()))((((()((()()((()((((())(((((()()((())((()(())())((((())(())))))(()((((())(())(((((((((()(((()(((())()()((((((())()(((((((()))(()(((())(((("

    808

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

  101. ")((()()((())())())(()(())))()()(()))))(()))()()))()()))())(()()(()()())(((((((()((())()(((((())))()))()))(((((())((())))()(()((()))())()))())()))()())"

    7908

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

  102. "))())))))))))))))))))())))())))))))))))))))))))))))))))())))()))()))))))))))))()))))))())))))))()()))))))))))))))))()))())))))))))))())))))))))))())()"

    161

    Returns: "()"

  103. "))()))()))()))))())))))))))())))()))))))))()()))(()()))))))())))))))))))()))))())))))())))))))))()))))())))))))()))())))))))))))))))))))))))))))())))("

    220

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

  104. "()((())())))))))((()()))))(((()()(((((()))()(()()))))))(())()()))))()))()()))(()))()(((())(()()()()()((()(()(())(()(())(())())(()(()())()))))()))(()))"

    8037

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

  105. "))()))))())(())))(())))()())))))())))))))))))())())()))))())(()))()()()))()))())()))))))()))))()))()())()))))()(())))()))))())))())))))))())))))))))))"

    232

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

  106. "())(()()))(((()())()((()((((()((()()(()(())((((())))()))))(((()(()))()()((()(()()))))(((((((((((()()))(()()())(())())((())(()(()))(())()()())))((((((("

    7219

    Returns: "()"

  107. "(()))(()())(((()()(()()((())())))()))((((((())))))()())))))(()))((()((((()))()))))(())(()(())())((())()()(())))(())())()()))(()((()))())())()))(()))(("

    742

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

  108. "())())()(()))()())))())()())))(()()))(())()(())()())((()))))((()))))))(())(())()))()(())))()(()(((())))()))(((()((())))(())))))))())((()(())(())()(()("

    1547

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

  109. ")()))((((((()()()))()))())((())()))())()(()(()((((((())(()())((((((())()))()())))))((())()(((()()))))))((((((()))(((((()))()(()(())())(())(((())))((()"

    4610

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

  110. ")(()()(()()()(((())()))(()())((()((()()())))(()()()()(()))((()())()))))))()(((())(())(()))(()()))(())()((()()(()()(((()((())()))((()())()())()))(((())"

    10867

    Returns: "()"

  111. "))())))()))(()())))())))))))))))))()))))())))))))))))))))))())))))())())))))())))))))))())))())))())))())))))))))))))))))(()())))())))()))))))))))))))"

    539

    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.
This problem was used for: