Statistics

Problem Statement for "ParenthesesDiv2Hard"

Problem Statement

Correct parentheses sequences can be defined recursively as follows:
  • The empty string "" is a correct sequence.
  • If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
  • If "X" is a correct sequence, then "(X)" is a correct sequence.
  • Each correct parentheses sequence can be derived using the above rules.
Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".


You are given a String s. You are also given int[]s L and R, each with the same number of elements. These encode a set of conditions. For each valid i, you have to satisfy the following condition: the substring of s that begins at the 0-based index L[i] and ends at the 0-based index R[i] must be a correct parentheses sequence. Note that the constraints guarantee that all the given ranges of indices are pairwise disjoint.


You can only modify s in one way: in each step you can choose two characters of s and swap them. Return the minimal number of swaps needed to produce a string that satisfies all the given conditions. If it is impossible, return -1 instead.

Definition

Class:
ParenthesesDiv2Hard
Method:
minSwaps
Parameters:
String, int[], int[]
Returns:
int
Method signature:
int minSwaps(String s, int[] L, int[] R)
(be sure your method is public)

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • Each character in s will be '(' or ')'.
  • L will contain between 1 and 50 elements, inclusive.
  • L and R will contain the same number of elements.
  • For each valid i, 0 <= L[i] <= R[i] < |s|.
  • For different i and j, intervals [(L[i]), (R[i])] and [(L[j]), (R[j])] will not intersect.

Examples

  1. ")("

    {0}

    {1}

    Returns: 1

    We have one condition: The substring that begins at index 0 and ends at index 1 must be a correct parentheses sequence. In this case, this means that the entire string s must be a correct parentheses sequence. We can achieve that by swapping s[0] with s[1]. This swap produces the string "()".

  2. "(())"

    {0,2}

    {1,3}

    Returns: 1

    The only way to satisfy both conditions is to change s into "()()". This can be done in 1 swap: by swapping s[1] with s[2].

  3. "(((())"

    {0,2}

    {1,3}

    Returns: 2

    This time we do swap(s[1],s[4]) and swap(s[3],s[5]).

  4. "((()()"

    {0,2}

    {1,3}

    Returns: 1

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

    {0,2}

    {1,3}

    Returns: -1

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

    {1,6,13,17,23,25}

    {4,7,16,20,24,28}

    Returns: 5

  7. "("

    {0}

    {0}

    Returns: -1

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

    {28, 24}

    {29, 27}

    Returns: 1

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

    {6}

    {41}

    Returns: 1

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

    {6, 30, 18, 0}

    {17, 35, 21, 5}

    Returns: 3

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

    {3, 28, 15, 0}

    {4, 39, 18, 1}

    Returns: 4

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

    {13, 8, 0}

    {36, 9, 1}

    Returns: 3

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

    {4}

    {39}

    Returns: 2

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

    {11, 30, 34}

    {22, 33, 35}

    Returns: 4

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

    {6}

    {41}

    Returns: 1

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

    {16, 0}

    {37, 7}

    Returns: 2

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

    {7, 15, 26}

    {10, 20, 41}

    Returns: 4

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

    {12, 18, 0, 22, 25}

    {13, 21, 1, 23, 30}

    Returns: 4

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

    {13, 25, 21, 1}

    {16, 26, 22, 2}

    Returns: 2

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

    {5, 28, 25, 22}

    {16, 29, 26, 23}

    Returns: 3

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

    {0, 24}

    {23, 27}

    Returns: 4

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

    {20, 24, 0}

    {23, 25, 3}

    Returns: 2

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

    {0, 23, 11, 2, 27, 14, 5, 19}

    {1, 24, 12, 3, 28, 15, 6, 20}

    Returns: 6

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

    {8, 25, 5, 2, 0}

    {23, 30, 6, 3, 1}

    Returns: 6

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

    {5, 23, 0, 20}

    {18, 26, 1, 21}

    Returns: 5

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

    {0, 29}

    {17, 30}

    Returns: 3

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

    {21, 2, 17, 7, 0}

    {30, 3, 18, 8, 1}

    Returns: 5

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

    {4, 0}

    {13, 1}

    Returns: 3

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

    {3, 0}

    {16, 1}

    Returns: 1

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

    {25, 7}

    {28, 10}

    Returns: 2

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

    {0}

    {29}

    Returns: 1

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

    {1, 18, 6, 14, 25, 10, 23}

    {2, 21, 7, 15, 26, 11, 24}

    Returns: 4

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

    {14, 20, 28, 25}

    {15, 21, 29, 26}

    Returns: 3

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

    {8, 19, 0, 4, 27, 16}

    {11, 20, 3, 5, 28, 17}

    Returns: 5

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

    {8, 25}

    {19, 28}

    Returns: 3

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

    {6, 1, 21, 17, 27, 24}

    {9, 2, 22, 18, 30, 25}

    Returns: 4

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

    {27, 9, 0, 7, 4}

    {30, 24, 3, 8, 5}

    Returns: 5

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

    {23, 1, 17}

    {30, 14, 18}

    Returns: 3

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

    {7, 0, 25, 22, 19}

    {14, 5, 26, 23, 20}

    Returns: 6

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

    {22, 28, 14, 2}

    {27, 29, 15, 5}

    Returns: 3

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

    {15, 0, 2}

    {16, 1, 3}

    Returns: 2

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

    {2, 12}

    {7, 13}

    Returns: 2

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

    {18, 22, 9, 0, 29}

    {19, 25, 10, 7, 30}

    Returns: 4

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

    {16, 4}

    {27, 13}

    Returns: 4

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

    {0, 14, 29, 9}

    {5, 19, 30, 10}

    Returns: 3

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

    {24}

    {29}

    Returns: 2

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

    {0, 14, 23, 29}

    {9, 17, 24, 30}

    Returns: 5

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

    {7, 12, 21, 27, 24}

    {8, 17, 22, 28, 25}

    Returns: 6

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

    {4, 0, 18, 27, 10, 13}

    {5, 1, 23, 28, 11, 14}

    Returns: 3

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

    {4, 11, 15, 29}

    {7, 14, 26, 30}

    Returns: 5

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

    {22, 9, 5}

    {27, 10, 6}

    Returns: 2

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

    {12, 3}

    {27, 8}

    Returns: 4

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

    {20, 24, 2, 15, 9}

    {23, 27, 7, 16, 10}

    Returns: 6

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

    {2}

    {11}

    Returns: 2

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

    {24, 0}

    {27, 23}

    Returns: 4

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

    {6, 0, 15, 29, 12}

    {11, 1, 24, 30, 13}

    Returns: 4

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

    {0, 6, 27}

    {1, 17, 28}

    Returns: 2

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

    {0}

    {5}

    Returns: -1

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

    {0, 12, 10}

    {3, 15, 11}

    Returns: -1

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

    {9, 12}

    {10, 13}

    Returns: 2

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

    {0}

    {9}

    Returns: -1

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

    {0}

    {15}

    Returns: -1

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

    {11, 6}

    {14, 7}

    Returns: -1

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

    {5}

    {14}

    Returns: -1

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

    {6, 4}

    {9, 5}

    Returns: 1

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

    {4}

    {11}

    Returns: 2

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

    {10}

    {11}

    Returns: -1

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

    {1}

    {14}

    Returns: -1

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

    {7}

    {8}

    Returns: 1

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

    {6, 2}

    {13, 3}

    Returns: -1

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

    {1}

    {10}

    Returns: 2

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

    {6, 0}

    {11, 3}

    Returns: -1

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

    {5, 11}

    {10, 12}

    Returns: 3

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

    {0, 4, 12}

    {3, 11, 15}

    Returns: -1

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

    {12, 0}

    {13, 1}

    Returns: -1

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

    {11, 6, 0}

    {14, 7, 5}

    Returns: 3

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

    {4}

    {13}

    Returns: -1

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

    {1, 6, 13, 17, 23, 25 }

    {4, 7, 16, 20, 24, 28 }

    Returns: 5

  79. "())"

    {0 }

    {1 }

    Returns: 0

  80. "(()))"

    {0, 2 }

    {1, 3 }

    Returns: 1

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

    {0, 2 }

    {1, 3 }

    Returns: -1

  82. "()()"

    {0 }

    {2 }

    Returns: -1

  83. "(())"

    {0, 2 }

    {1, 3 }

    Returns: 1

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

    {1, 6, 13, 17, 23, 25 }

    {4, 7, 16, 20, 24, 28 }

    Returns: 7

  85. "()"

    {0 }

    {1 }

    Returns: 0

  86. "))(("

    {0 }

    {1 }

    Returns: 1

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: