Pseudo-code

text
Queue q
Set visited
q.add(initial_string, swaps=0)

while q is not empty:
    curr, swaps = q.pop()
    if isBalanced(curr):
        return swaps
    
    for i from 0 to n:
        for j from i+1 to n:
            next_str = swap(curr, i, j)
            if next_str not in visited:
                q.add(next_str, swaps + 1)
                visited.add(next_str)

Complexity Analysis

• Time Complexity: Factorial/Exponential. The number of permutations is huge, and the branching factor is $O(N^2)$. With $N$ up to $10^6$, this is impossible.
• Why it fails: The constraints ($N \le 10^6$) require an $O(N)$ or $O(N \log N)$ solution. The search space for swaps is astronomically large, leading to an immediate .

Core Insight for Minimum Number of Swaps to Make the String Balanced

The intuition behind the optimal solution is cancellation. We don't need to simulate the swaps physically. Instead, we only need to quantify how "unbalanced" the string is.

When we process the string using the standard Valid Parentheses logic, we pair every closing bracket ] with the nearest available opening bracket [ before it. If we remove all such valid pairs, we are left with a "reduced" string that cannot be simplified further.

Because the original string has an equal number of [ and ], the reduced string will always follow a specific structure:

1. A sequence of unmatched closing brackets ].
2. Followed by an equal number of unmatched opening brackets [.

For example, ]]][[[. This reduced form consists of $k$ closing brackets followed by $k$ opening brackets.

The Key Calculation: One swap can fix two pairs of mismatched brackets in the optimal case. Consider the reduced form ]][[.

• Swapping the first ] with the last [ transforms it into [[]].
• This single swap fixed the entire imbalance.

For a generic reduced string of $k$ unmatched pairs (e.g., ]]]...[[[), we need $\lceil k / 2 \rceil$ swaps. The formula is: $\text{Swaps} = \frac{\text{unmatched\_pairs} + 1}{2}$ where integer division is used.

Visual Description: Imagine iterating through the string. Every time you encounter a [, you place a token on a stack. Every time you encounter a ], you check the stack. If there is a token, you remove it (a valid pair is formed and vanishes). If the stack is empty, that ] is a permanent mismatch in the current configuration. At the end of the traversal, the number of tokens remaining on the stack represents the count of [ that never found a closing partner.

Execution Flow

Let's trace the algorithm with Example 2: s = "]]][[[".

1. Initialize: stack_size = 0.
2. Index 0 (]): stack_size is 0. No match possible. (Conceptually, this is a mismatch).
3. Index 1 (]): stack_size is 0. No match.
4. Index 2 (]): stack_size is 0. No match.
5. Index 3 ([): Increment stack_size to 1.
6. Index 4 ([): Increment stack_size to 2.
7. Index 5 ([): Increment stack_size to 3.
8. End of Loop: stack_size is 3. This means we have 3 unmatched [ brackets (and implicitly 3 unmatched ]).
9. Calculation: (3 + 1) / 2 = 2.
10. Result: Return 2.

Trace with s = "][][":

1. stack_size = 0.
2. ] -> No match.
3. [ -> stack_size = 1.
4. ] -> Match found! stack_size becomes 0.
5. [ -> stack_size = 1.
6. End: stack_size is 1.
7. Calculation: (1 + 1) / 2 = 1.

Proof of Correctness

Why does (k + 1) / 2 work?

After removing all valid pairs, the string reduces to the form ]...][...[ with $k$ closing brackets followed by $k$ opening brackets. The most efficient way to fix this is to swap the first unmatched ] with the last unmatched [.

• Original reduced form: ] ... [.
• After swap: [ ... ].
• The new [ at the beginning and the ] at the end form a valid pair [...] that wraps the remaining substring.
• This action effectively creates one valid pair and allows the inner contents to potentially match.
• Mathematically, one swap reduces the count of unmatched pairs ($k$) by 2.
• Therefore, we need $\lceil k / 2 \rceil$ swaps.

Reference Implementation

C++ Solution for LeetCode 1963

cpp
class Solution {
public:
    int minSwaps(string s) {
        // 'stackSize' tracks the number of unmatched opening brackets '['
        int stackSize = 0;
        
        for (char c : s) {
            if (c == '[') {
                stackSize++;
            } else {
                // If we encounter ']', we try to match it with a previous '['
                if (stackSize > 0) {
                    stackSize--;
                }
                // If stackSize is 0, this ']' is unmatched, 
                // but we don't need to track it explicitly for the formula.
            }
        }
        
        // The number of unmatched pairs is stackSize.
        // Each swap fixes 2 pairs. 
        // Formula: ceil(stackSize / 2) which is (stackSize + 1) / 2 using integer math.
        return (stackSize + 1) / 2;
    }
};

Java Solution for LeetCode 1963

java
class Solution {
    public int minSwaps(String s) {
        // 'stackSize' simulates a stack of opening brackets
        int stackSize = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '[') {
                stackSize++;
            } else {
                // If c is ']', check if we have a matching '['
                if (stackSize > 0) {
                    stackSize--;
                }
            }
        }
        
        // stackSize now represents the number of unmatched '[' brackets.
        // We need ceil(stackSize / 2) swaps.
        return (stackSize + 1) / 2;
    }
}

Python Solution for LeetCode 1963

python
class Solution:
    def minSwaps(self, s: str) -> int:
        # stack_size tracks the number of unmatched '['
        stack_size = 0
        
        for c in s:
            if c == '[':
                stack_size += 1
            else:
                # c is ']'
                if stack_size > 0:
                    stack_size -= 1
        
        # stack_size is the number of remaining unmatched '['
        # Return ceil(stack_size / 2)
        return (stack_size + 1) // 2