**Problem Link:** contest, practice

**Difficulty:** Cakewalk

**Pre-requisites:** Basics

**Problem:**

Given a valid parentheses sequence **A**. Your task is to find another valid parentheses sequence **B** with the minimal possible length, such that the maximal balance over all prefixes of **A** is equal to the same characteristic of **B**.

**Explanation:**

This problem requires some logical thinking and being familiar with valid parentheses sequences.

Let’s consider a pseudocode that has been provided to you in the statement:

FUNCTION F( S - a valid parentheses sequence ) BEGIN balance = 0 maxbalance = 0 FOR index FROM 1 TO LENGTH(S) BEGIN if S[index] == '(' then balance = balance + 1 if S[index] == ')' then balance = balance - 1 maxbalance = max( maxbalance, balance ) END RETURN maxbalance END

The first observation is that there should be at least **maxbalance** open brackets in **B**. Every open bracket should also have a paired closed bracket, so the length of **B** is at least 2 * **maxbalance**. Fortunartely, there’s a valid **B** with the length equal to 2 * **maxbalance**, it looks like this: the first **maxbalance** brackets are open brackets, the last **max_balance** brackets are closed ones. It isn’t hard to prove that this is the only way to construct **B** with such a length.

So, here are the keypoints of the solution:

- Determing the value of
**maxbalance**; -
**B**is**maxbalance**open brackets and**maxbalance**closed brackets concatenated together.

Complexity is **O(N)** per a testcase.

Please, check out Setter’s and Tester’s solutions for your better understanding.

**Setter’s Solution:** link

**Tester’s Solution:** link