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 bothA
andB
are balanced strings, or - It can be written as
[C]
, whereC
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']'
. - The number of opening brackets
'['
equalsn / 2
, and the number of closing brackets']'
equalsn / 2
.
SOLUTION:
class Solution:
def minSwaps(self, s: str) -> int:
stack = []
err = 0
for c in s:
if c == '[':
stack.append(c)
elif c == ']':
if len(stack) > 0:
stack.pop()
else:
err += 1
return (err + 1) // 2
Top comments (1)
Found this helpful. Thanks for sharing.