Minimum bracket reversals to balance an expression
Problem
The expression contains only { and }. Reversing a bracket changes { to } or } to {. Return the minimum number of reversals needed to balance it, or −1 if that is impossible (an odd length).
Example 1
Input: "}{{}}{{{"
Output: 3Example 2
Input: "{{{"
Output: -1Also asked as: Minimum number of bracket reversals needed to make an expression balanced
Test cases
Case 1
Input: "}{{}}{{{"
Expected: 3Case 2
Input: "}{"
Expected: 2Case 3
Input: "{{}}"
Expected: 0Case 4
Input: "{{{"
Expected: -1View solutionHide solution1 approach
1. Reduce, then count leftover open/close
Time O(n)Space O(1)
Cancel every matched "()". From the leftover "}}}...{{{" with c closers and o openers, the answer is ceil(c/2) + ceil(o/2).
function minReversals(s) { if (s.length % 2) return -1; let open = 0, close = 0; for (const c of s) { if (c === '{') open++; else if (open > 0) open--; // matched a pair else close++; // an unmatched '}' } return Math.ceil(open / 2) + Math.ceil(close / 2);}