Strings Parentheses and nesting
136. Fewest Bracket Flips
You are given a string s made of ( and ). A flip turns one character into the other: a (
becomes ), or a ) becomes (.
Return the fewest flips that make s balanced. A string is balanced when its parentheses are properly
nested: every ( is closed by a later ), and every ) closes an earlier (.
A flip never changes the length of s, and a balanced string always has an even length. So when s has
an odd length, no number of flips can balance it. Return -1 in that case.
Example 1
Input: s = ")(()))(("
2Explanation: Flip the first character to ( and the last one to ). The string becomes ((()))(), which is
balanced. One flip is not enough.
Example 2
Input: s = ")))("
3Explanation: Flip the characters at indexes 0 and 2 to (, and the one at index 3 to ). The string becomes
()().
Example 3
Input: s = "(()"
-1Explanation: The length is 3, which is odd, so no number of flips can balance it.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ s.length ≤ 105sholds only the characters(and).
Clarifying questions
What you would ask an interviewer before writing any code.