Statistics

Problem Statement for "JustBrackets"

Problem Statement

Hero has a String s that is guaranteed to be a correct bracket sequence (see Notes for a definition). Hero can perform the following operation: he can choose a substring of the form "()" and erase it. For example, he can change "(())()" into either "()()" or "(())" by erasing either the first or the second occurrence of the substring "()". Find and return the lexicographically smallest non-empty string Hero can produce from s by performing the operation zero or more times.

Definition

Class:
JustBrackets
Method:
getSmallest
Parameters:
String
Returns:
String
Method signature:
String getSmallest(String s)
(be sure your method is public)

Notes

  • Given two distinct strings A and B, we say that A is lexicographically smaller than B if either A is a prefix of B, or there is a nonnegative integer x such that the first x characters of A match the first x characters of B, and the next character of A is smaller than the next character of B.
  • Correct bracket sequences include the empty string and everything that can be derived using the following rule: if S and T are correct bracket sequences then both (S) and ST are also correct bracket sequences.

Constraints

  • s will contain between 2 and 100 characters, inclusive.
  • Each character in s will be either '(' or ')'.
  • s will be a correct bracket sequence.

Examples

  1. "()"

    Returns: "()"

    As we are looking for a non-empty string, Hero cannot erase the last pair of brackets.

  2. "()()"

    Returns: "()"

  3. "(())"

    Returns: "(())"

    Even though Hero could erase one pair of brackets, it is better not to do so: the string "(())" is lexicographically smaller than the string "()".

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

    Returns: "((()))"

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

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

  6. "()()(((()()()()()()(())()(()()((()))((()))()()()()())))())()(())(()(()))()()(())()()"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Returns: "(()())"

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

    Returns: "((()))"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  65. "(())(()()()()(()(((())))(()))()()()()())"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Returns: "(())"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Returns: "((()))"

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

    Returns: "()"

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

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

  93. "()(())"

    Returns: "(())"

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

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

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

    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: