Swapping Brackets Into Balance

Medium

You get a string brackets of even length n with exactly n / 2 opening brackets [ and exactly n / 2 closing brackets ]. A bracket string is balanced when every opening bracket can be paired with a closing bracket to its right so that pairs never cross, as in [[]] or [][] but not in ][ or []][. In one move you may swap any two characters of the string. Return the fewest moves that make brackets balanced.

Example 1

brackets="]][[" → 1

Swap the characters at indices 0 and 3 to get [][].

Example 2

brackets="[][]" → 0

The string is already balanced.

Example 3

brackets="]]]][[[[" → 2

Swapping indices 0 and 7 gives []]][[[], then swapping indices 2 and 5 gives [][][][]. One swap is not enough.

Constraints

2 ≤ len(brackets) ≤ 10⁶, the length is even
brackets consists only of [ and ]
There are as many opening brackets as closing ones

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Greedy Two Pointers String

Similar problems

Every Letter Once Medium Erase Digits for the Smallest Number Medium Smallest Up-Down Sequence Medium Fix the Middle of the Line Medium Brackets With Wildcards Medium

Input

brackets="]][["

Expected

Run checks the first 3 tests in your browser. Submit checks all 34 tests on the server, hidden ones included.