ParenthesesDiv2Medium | Topcoder Archive

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 have a String s of length n, where n is even. Your task is to change it into a correct parentheses sequence. In order to do that, you are allowed to flip some parentheses. Flipping a parenthesis changes it from '(' to ')' and vice versa.

There is always a way to change s into a correct parentheses sequence by doing at most (n/2)+1 flips. Find any such sequence of flips. Return a int[] containing a sequence of 0-based indices of parentheses in s you want to flip.

Definition

Class:: ParenthesesDiv2Medium
Method:: correct
Parameters:: String
Returns:: int[]
Method signature:: int[] correct(String s)
(be sure your method is public)

Constraints

s will contain between 2 and 50 characters, inclusive.
The length of s will be even.
Each character in s will be '(' or ')'.

Examples

```
")("
```
```
Returns: {0, 1 }
```
The returned sequence represents the following sequence of changes: Start with the string ")(". Flip character 0. This produces the string "((". Flip character 1. This produces the string "()", which is a corrent parentheses sequence.
```
")))))((((("
```
```
Returns: {0, 2, 4, 5, 7, 9 }
```
Performing the flips described by the returned sequence changes the given string into the corrent parentheses sequence "()()()()()". The answer {2, 0, 4, 9, 7, 5} would also be valid, as the order in which we perform the flips does not matter. However, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} is not a valid answer: this sequence of flips does produce a correct parentheses sequence but the number of flips is too large. As the length of s is 10, we may only perform at most 10/2 + 1 = 6 flips.
```
"((()"
```
```
Returns: {1 }
```
```
")))(()(())))))"
```
```
Returns: {0, 1, 2 }
```
Here, {0, 1, 2, 3, 3} would also be a valid answer. Flipping the same parenthesis twice is allowed, even though it is clearly useless.

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

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.