FunctionRacerProblemsRace

Fewest Flips to Balance Brackets

MediumGreedyPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Greedy problems