665. Minimum Swaps to Make String Balanced

Given a string s of equal numbers of '[' and ']', in one swap you may exchange any two characters. Return the minimum number of swaps to make s a balanced bracket string. The input is JSON {s}.

Input: JSON {s}.

Output: Integer — the minimum swaps.

Examples

Input: {"s":"][]["}
Output: 1
Explanation: One swap balances it.

Input: {"s":"]]][[["}
Output: 2
Explanation: Two swaps needed.

Input: {"s":"[]"}
Output: 0
Explanation: Already balanced.

Constraints

• 2<=|s|<=10^6
• even length, equal brackets

Asked by