Minimum Number of Swaps to Make the String Balanced
You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.
A string is called balanced if and only if:
- It is the empty string, or
- It can be written as
AB, where bothAandBare balanced strings, or - It can be written as
[C], whereCis a balanced string.
You may swap the brackets at any two indices any number of times.
Return the minimum number of swaps to make s balanced.
Example 1
Input
s = "][]["Output
1You can make the string balanced by swapping index 0 with index 3, resulting in "[[]]".
Example 2
Input
s = "]]][[["Output
2After swapping index 0 with index 4 and index 1 with index 5, the resulting string is "[[][]]".
Constraints
- n == s.length
- 2 <= n <= 10^6
- n is even.
- s[i] is either '[' or ']'.
- The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 2.