117. Minimum number of bracket reversals to make an expression balanced
Given a string s consisting of only opening and closing brackets '(' and ')', find out the minimum number of reversals required to convert the string into a balanced expression.
If it is not possible to make the brackets balanced, return -1. A reversal means changing '(' to ')' or vice-versa.
A balanced expression is a string where:
- It is empty, or
- Every opening bracket '(' has exactly one corresponding closing bracket ')'
- Every closing bracket ')' has exactly one corresponding opening bracket '('
- Brackets are properly nested, meaning every opened bracket is closed before any outer bracket is closed
Example 1:
Input: s = ")(())((("
Output: 3
Explanation: One way to balance is:
"((())())". There is no balanced sequence
that can be formed in lesser reversals.
Example 2:
Input: s = "(()((()(())(("
Output: -1
Explanation: There's no way we can balance
this sequence of braces.
Now Your Turn!
Pick the correct output for the given inputInput: s="((())())"
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= s.length <= 104