Medium
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:
AB
, where both A
and B
are balanced strings, or[C]
, where C
is 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: 1
Explanation: You can make the string balanced by swapping index 0 with index 3. The resulting string is “[[]]”.
Example 2:
Input: s = “]]][[[”
Output: 2
Explanation: You can do the following to make the string balanced:
Swap index 0 with index 4. s = “[]][][”.
Swap index 1 with index 5. s = “[[][]]”. The resulting string is “[[][]]”.
Example 3:
Input: s = “[]”
Output: 0
Explanation: The string is already balanced.
Constraints:
n == s.length
2 <= n <= 106
n
is even.s[i]
is either '['
or ']'
.'['
equals n / 2
, and the number of closing brackets ']'
equals n / 2
.public class Solution {
public int minSwaps(String s) {
int openCount = 0;
int swap = 0;
for (char c : s.toCharArray()) {
if (c == '[') {
openCount++;
} else {
if (openCount == 0) {
swap++;
openCount++;
} else {
openCount--;
}
}
}
return swap;
}
}