Welcome to Subscribe On Youtube
1963. Minimum Number of Swaps to Make the String Balanced
Description
You are given a 0indexed 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 <= 10^{6}
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)$.

class Solution { public int minSwaps(String s) { int x = 0; for (int i = 0; i < s.length(); ++i) { char c = s.charAt(i); if (c == '[') { ++x; } else if (x > 0) { x; } } return (x + 1) / 2; } }

class Solution { public: int minSwaps(string s) { int x = 0; for (char& c : s) { if (c == '[') { ++x; } else if (x) { x; } } return (x + 1) / 2; } };

class Solution: def minSwaps(self, s: str) > int: x = 0 for c in s: if c == "[": x += 1 elif x: x = 1 return (x + 1) >> 1

func minSwaps(s string) int { x := 0 for _, c := range s { if c == '[' { x++ } else if x > 0 { x } } return (x + 1) / 2 }

function minSwaps(s: string): number { let x = 0; for (const c of s) { if (c === '[') { ++x; } else if (x) { x; } } return (x + 1) >> 1; }