DSA interview question

Minimum Number of Bracket Reversals to Make an Expression Balanced

Hard · Data structures · Topics: string, stack, greedy

The problem

You're building a syntax auto-repair tool for an in-house config-file linter (think: JSON-like or expression configs where brackets occasionally get mistyped due to copy-paste errors or merge conflicts). Given a string consisting only of { and } characters, your tool needs to figure out the minimum number of bracket reversals (flipping a { to } or vice versa) needed to make the expression balanced. If the total length of the string is odd, it's impossible to balance — return -1 in that case.

Example: s = "}{{}}{{{" → minimum 3 reversals needed.

Function signature

int minBracketReversals(string s);

Test cases

Input `s`	Output	Explanation
`"}{{}}{{{"`	`3`	Needs 3 flips to balance
`"{{}}"`	`0`	Already balanced
`"}}}}"`	`2`	Flip two `}` to `{` → `"{{}}"` style balance, 4/2=2 flips
`"}{"`	`2`	Single mismatched pair needs 2 flips (one `{`-type, one `}`-type imbalance)
`"{{{"`	`-1`	Odd length — impossible to balance
`""`	`0`	Empty string is trivially balanced
`"{}"`	`0`	Already balanced
`"}{}{"`	`2`	Needs 2 flips

(Note: this problem assumes only { and } — no need to track multiple bracket types like ()[].)

How interviewers phrase it

"Given a string of only { and }, find the minimum number of bracket flips needed to balance it."
"You're given an unbalanced bracket sequence — each operation lets you flip a bracket's direction. What's the fewest flips to make it valid?"
Often used as a stack warm-up problem before escalating to harder bracket/parenthesis variants (e.g., "minimum additions to make valid," "longest valid parentheses").

Clarifying questions to ask

Is the string guaranteed to contain only { and } (no other bracket types like ()[]mixed in)? (Confirm — this problem is specifically simplified to one bracket type.)
What counts as a "reversal" — can I only flip { to } (and vice versa), not insert/delete characters? (Confirm — this is distinct from "minimum insertions to balance," a different problem.)
What should be returned if the string length is odd? (Standard convention: -1, since balance requires equal counts of some even total length — confirm.)
Is the empty string considered balanced (and thus needs 0 reversals)?
Should I assume well-formed input (only {/} characters), or do I need to validate/sanitize input first?

Follow-ups to expect

"Walk through why an odd-length string is always impossible to balance."
"Can you solve this without a stack, just using counters?"
"Derive the formula for combining a leftover }} pair and a leftover {{ pair into a single reversal count."
"What if the string also contains other bracket types like () and []? How would your approach change?"
"Can you do this in O(1) space instead of O(n) with a stack?"
"Prove your greedy approach gives the minimum number of reversals, not just a valid one."

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview