LeetCode 1963. Minimum Number of Swaps to Make the String Balanced Solution in Java, C++, Python & More | Explanation + Code

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 both A and B are balanced strings, or
• It can be written as [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 ']'.
• The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 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 ^{x + 1}⁄₂ \right\rfloor.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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

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