Fewest Flips to Balance Brackets
s consists only of ( and ) and has even length. One flip turns a single ( into ) or a single ) into (. The string is balanced when, reading left to right, the count of ) never exceeds the count of (, and the two counts are equal at the end.
Return the fewest flips that make s balanced. The fewest number of flips is unique, so no tie rule is needed. Return 0 for the empty string.
Example 1
s "(()))("
returns 2
Flip the fifth character to get (())(): the third ) had nothing to close, and the final ( had nothing to close it.
Example 2
s "))(("
returns 2
Flip the first and third characters: (()) is balanced and no single flip works.
Constraints
0 <= len(s) <= 60len(s)is evenshas only(and)
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Greedy problems
- Fewest Increments to Distinct ValuesMedium
- Fewest Jumps to the EndMedium
- Fewest PlatformsMedium
- Fewest Routers for a CorridorMedium
- Jump GameMedium
- Largest Tidy Number BelowMedium
- Make Letter Counts DistinctMedium
- Most Fairs VisitedMedium