Minimum bracket reversals to balance an expression

Medium

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: 3

Example 2

Input:  "{{{"
Output: -1

Also asked as: Minimum number of bracket reversals needed to make an expression balanced

Test cases

Case 1

Input:    "}{{}}{{{"
Expected: 3

Case 2

Input:    "}{"
Expected: 2

Case 3

Input:    "{{}}"
Expected: 0

Case 4

Input:    "{{{"
Expected: -1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View 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);
}