# Minimum Number of Swaps to Make the String Balanced
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-swaps-to-make-the-string-balanced
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Stack
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia), [Nutanix](https://scaleengineer.com/companies/nutanix), [PayPal](https://scaleengineer.com/companies/paypal), [Microstrategy](https://scaleengineer.com/companies/microstrategy), [Twilio](https://scaleengineer.com/companies/twilio)
---
## Problem
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`.

# Approaches
## Stack-Based Mismatch Identification
This approach uses a stack to identify all the brackets that are not part of a balanced subsequence. By filtering out the correctly matched `[]` pairs, we are left with a sequence of mismatched brackets. The number of swaps can then be determined from the count of these mismatched brackets.
**Time:** O(N), as we perform a single pass through the string. Stack operations (push, pop, peek) take O(1) time. · **Space:** O(N), where N is the length of the string. In the worst case, such as for a string like `"[[[[...]]]]"`, the stack can grow to a size of N.
**Pros:** The logic is intuitive as it directly models the process of pairing brackets.; It correctly identifies the exact set of mismatched brackets.
**Cons:** Requires extra space that can be proportional to the input size in the worst-case scenarios.
### Explanation
The fundamental property of a balanced string is that any closing bracket `]` must be preceded by a matching opening bracket `[`. We can use a stack to keep track of the unmatched opening brackets.

When we encounter an opening bracket `'['`, we push it onto the stack. When we see a closing bracket `']'`, we check if there's a matching `'['` at the top of the stack. If so, we've found a balanced pair `[]`, and we can pop the stack, effectively removing this pair. If the stack is empty or the top is not `'['`, it means the current `']'` is mismatched in its current position. In this case, we also push it onto the stack to mark it as part of the mismatched group.

After one pass, the stack contains all the brackets that couldn't be paired up. Because the original string had an equal number of `[` and `]`, the stack will also have an equal number of them, say `k` of each. The structure on the stack will be `k` closing brackets followed by `k` opening brackets (`]]...]][[...[`). The total size of the stack is `2k`. The number of mismatched pairs is `k`.

To make this sequence of `2k` brackets balanced, we need to perform swaps. It can be shown that for `k` mismatched pairs, the minimum number of swaps required is `ceil(k / 2.0)`. For example, `]][[` (`k=2`) needs 1 swap to become `[[]]`. `]]][[[` (`k=3`) needs 2 swaps. This can be calculated with integer arithmetic as `(k + 1) / 2`.

```java
import java.util.Stack;

class Solution {
    public int minSwaps(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '[') {
                stack.push(c);
            } else { // c == ']'
                if (!stack.isEmpty() && stack.peek() == '[') {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }
        
        // The stack now contains all mismatched brackets.
        // The number of mismatched pairs is half the size of the stack.
        int mismatchedPairs = stack.size() / 2;
        
        // The number of swaps for k mismatched pairs is ceil(k / 2.0).
        return (mismatchedPairs + 1) / 2;
    }
}
```
### Algorithm
- Initialize an empty `Stack<Character>`.
- Iterate through the input string `s` character by character.
- If the current character is `'['`, push it onto the stack.
- If the current character is `']'`: 
  - Check if the stack is not empty and its top element is `'['`. 
  - If it is, a `[]` pair is formed, so pop from the stack.
  - Otherwise, this `']'` is currently mismatched, so push it onto the stack.
- After iterating through the entire string, the stack will contain only the mismatched brackets, in the form of `]]...]][[...[`.
- The number of mismatched pairs, let's call it `k`, is half the size of the final stack (since each pair consists of one `[` and one `]`).
- The minimum number of swaps required is the ceiling of `k / 2`, which can be calculated using integer arithmetic as `(k + 1) / 2`.

## Greedy Single-Pass with a Counter
A more optimal approach avoids the use of a stack and instead relies on a simple counter to track the balance of brackets. By iterating through the string once, we can count the number of 'misplaced' closing brackets, which directly gives us the number of mismatched pairs. This achieves the same result with constant extra space.
**Time:** O(N), where N is the length of the string, because it involves a single loop through the string. · **Space:** O(1), as it only uses a few integer variables for counting, regardless of the input string size.
**Pros:** Extremely efficient in terms of memory, using only O(1) extra space.; Simple and fast, requiring only a single pass through the string.
**Cons:** The derivation of the final formula `(k + 1) / 2` is not immediately obvious without analyzing the swap patterns.
### Explanation
This approach is based on a greedy strategy. We iterate through the string and maintain a `balance` counter, which represents the number of open brackets that are waiting for a closing bracket. 

When we encounter an `'['`, we increment the balance. When we see a `']'`, we check the balance. If `balance > 0`, we can use one of the open brackets to form a pair, so we decrement the balance. However, if `balance` is 0, it means we have encountered a `']'` without a preceding `'['` to match it. This `']'` is misplaced. We count these misplaced closing brackets using a `mismatched_close` counter.

Since the total number of `'['` and `']'` in the string is equal, every misplaced `']'` must correspond to a misplaced `'['` that appears later in the string. Therefore, the `mismatched_close` count at the end of the iteration is exactly the number of mismatched pairs, `k`.

As established in the previous approach, the minimum number of swaps to fix `k` mismatched pairs is `ceil(k / 2.0)`. This can be calculated using integer division as `(k + 1) / 2`. This greedy method allows us to find `k` in a single pass with O(1) extra space, making it highly efficient.

```java
class Solution {
    public int minSwaps(String s) {
        int mismatchedClose = 0;
        int balance = 0; // Represents unmatched open brackets

        for (char c : s.toCharArray()) {
            if (c == '[') {
                balance++;
            } else { // c == ']'
                if (balance > 0) {
                    // This ']' can be matched with a previous '['
                    balance--;
                } else {
                    // This ']' is mismatched, no preceding '[' to pair with.
                    // It forms a mismatched pair with a '[' that must appear later.
                    mismatchedClose++;
                }
            }
        }

        // mismatchedClose now holds the number of mismatched pairs, k.
        // The number of swaps for k pairs is ceil(k/2.0).
        return (mismatchedClose + 1) / 2;
    }
}
```
### Algorithm
- Initialize two integer variables: `balance = 0` and `mismatched_close = 0`.
- Iterate through the string `s` from left to right.
- If the current character is `'['`, increment `balance`.
- If the current character is `']'`: 
  - If `balance > 0`, it means there is an unmatched open bracket available to form a pair. Decrement `balance`.
  - If `balance == 0`, this closing bracket does not have a preceding open bracket to match with. It is therefore part of a mismatched pair. Increment `mismatched_close`.
- After the loop, `mismatched_close` will hold the total number of mismatched pairs, `k`.
- The minimum number of swaps is `(k + 1) / 2`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```