64. Minimum Bracket Reversals to Balance an Expression

Given a string s made only of the characters { and }, find the minimum number of brackets you must reverse (change { to } or } to {) so the whole string becomes balanced. If the length of s is odd, balancing is impossible - print -1.

Input: The input is a single line containing a string s made only of '{' and '}' characters; it may be empty. Output: Print the minimum number of bracket reversals needed to balance s, or print -1 if balancing is impossible.

0 <= |s| <= 10^5

Checking for an ODD total length FIRST is a fast, cheap way to immediately rule out impossible cases before doing any further work.

Given a string of only { and } characters, find the fewest bracket 'flips' (changing a { to } or vice versa) needed to make the whole thing balanced. Brute force: Try every possible combination of which brackets to flip directly, checking if the result balances - this is exponential in the number of brackets, completely impractical. Optimised: After cancelling out every properly nested '{...}' pair, what's left is ALWAYS a clean run of unmatched '}' followed by unmatched '{' (never any other pattern) - and fixing two same-type leftovers with a single flip (turning one '{' among leftover '{'s into a '}', or vice versa) is always possible and always optimal, giving the direct ceil(m/2)+ceil(n/2) formula.

Repeatedly scan the string for any place where the brackets are unbalanced (for example, an unmatched closing brace appearing before its matching opening brace), flip one bracket to fix that specific local problem, and then re-scan the entire string from the beginning to check whether it is now balanced, repeating until it is (or determining it's impossible). This eventually finds a valid answer, but re-validating the whole string after every single fix wastes a lot of repeated work. Time: O(n^2) Space: O(1)

If the length is odd, answer -1. Otherwise scan the string once with a simple counter (like bracket-depth tracking): increment it on '{' and decrement on '}', and whenever it would go negative, that '}' is unmatched, so increment an 'unmatched closing' counter and reset the running counter to 0; whatever remains positive at the end is the count of unmatched '{'. Because the residual sequence is always of the form }}}...{{{, the answer is ceil(unmatched_closing / 2) + ceil(unmatched_opening / 2) (each reversal of a '}' to '{' or vice versa can fix one from each side, or one lone bracket needs two reversals). This produces the identical answer without ever building an explicit stack. Time: O(n) Space: O(1)

If the length is odd, immediately answer -1. Otherwise use a stack: scan the string, pushing '{' onto the stack, and whenever a '}' is seen with a '{' on top of the stack, pop it (they cancel as a matched pair); otherwise push the '}' too. After the scan, the stack contains only a residue of the form '}}}...{{{' representing brackets that don't have a natural match. Then make a second pass over this residue, pairing up leftover brackets and counting how many reversals each pairing needs. This finds the same answer as brute force scanning in one pass over the string plus a cleanup pass, at the cost of maintaining an explicit stack. Time: O(n) Space: O(n)

1. If the string's length is odd, balancing is flatly impossible - answer -1 immediately. 2. Repeatedly cancel out matching '{...}' pairs (conceptually, using a stack or simple counting), leaving behind only a 'leftover' run of unmatched closing brackets followed by unmatched opening brackets. 3. If m unmatched opening brackets and n unmatched closing brackets remain, the answer is ceil(m/2) + ceil(n/2) - each pair of two same-type leftovers can be fixed with just ONE flip (flip one of them to the other type).

Time: O(n) - one pass to cancel matching pairs (via a stack or counter) and tally the leftover unmatched brackets. Space: O(n) in the worst case if using an explicit stack (or O(1) if just counting unmatched brackets with running counters, since the specific nesting structure doesn't matter here, only the final leftover counts).

An empty string (0 reversals); odd-length s (always -1); leftover unmatched '{' or '}' counts that are themselves odd, requiring the ceil(m/2)+ceil(n/2) rounding; s up to 10^5 characters for performance.

Be ready to justify the ceil(m/2)+ceil(n/2) formula concretely with a small example - interviewers often push on WHY it's exactly this formula and not, say, just (m+n)/2.