1963. Minimum Number of Swaps to Make the String Balanced
Description
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
.
Solutions
Solution 1: Greedy
We use a variable $x$ to record the current number of unmatched left brackets. We traverse the string $s$, for each character $c$:
- If $c$ is a left bracket, then we increment $x$ by one;
- If $c$ is a right bracket, then we need to check whether $x$ is greater than zero. If it is, we match the current right bracket with the nearest unmatched left bracket on the left, i.e., decrement $x$ by one.
After the traversal, we will definitely get a string of the form "]]]...[[[..."
. We then greedily swap the brackets at both ends each time, which can eliminate $2$ unmatched left brackets at a time. Therefore, the total number of swaps needed is $\left\lfloor \frac{x + 1}{2} \right\rfloor$.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|