LeetCode Problem 1963

Difficulty: 🟡 Medium
Topics: Two Pointers, String, Stack, Greedy

Solution

Problem Understanding

The problem asks us to transform a given string of brackets into a balanced string with the minimum number of swaps. The input string s consists of n characters, where n is even, and there are exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'. A string is balanced if every opening bracket has a matching closing bracket and the brackets are properly nested according to the rules of a well-formed sequence.

In other words, at any point from the start to the end of the string, the number of opening brackets encountered should never be fewer than the number of closing brackets encountered. If this condition is violated, we need to perform swaps to fix it. The output is a single integer representing the minimum number of swaps required to achieve this balance.

The constraints indicate that n can be very large, up to 10^6, which means solutions with complexity worse than O(n) may not be feasible. The problem guarantees an equal number of opening and closing brackets, so we do not need to handle strings with mismatched counts, simplifying the implementation.

Important edge cases include strings that are already balanced, strings that are completely reversed like "]][[", and strings where only one swap is necessary at the start or end.

Approaches

A brute-force approach would try to find every unbalanced position and swap it with a correct bracket. For example, we could iterate through the string and whenever a closing bracket appears without a matching opening bracket to its left, we scan forward to find an opening bracket to swap. While this approach would eventually produce a balanced string, it requires repeated scanning and swapping, resulting in O(n^2) time complexity, which is too slow for n = 10^6.

The key insight for an optimal solution is that we do not need to simulate every swap. We only need to track the balance of the string as we iterate from left to right. Define a balance counter that increases by 1 for '[' and decreases by 1 for ']'. Whenever balance becomes negative, it means we have more closing brackets than opening brackets at that point, which will require swaps to fix. Each time balance drops below zero, we increment a swaps counter and reset the deficit to zero for the next steps. The final answer can be derived directly from the maximum deficit encountered, which corresponds to the minimum number of swaps needed.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Scan for misplaced brackets and swap; correct but too slow for large inputs
Optimal	O(n)	O(1)	Track balance and max deficit; each deficit requires a swap; very efficient

Algorithm Walkthrough

1. Initialize two variables: balance = 0 to track the net number of opening brackets, and max_deficit = 0 to track the largest negative balance encountered.
2. Iterate over each character c in the string s.
3. If c is '[', increment balance by 1.
4. If c is ']', decrement balance by 1.
5. After updating balance, if it is negative, it indicates that we have more closing brackets than opening brackets at this position. Update max_deficit to the absolute value of the current balance if it is larger than the current max_deficit.
6. At the end of the iteration, max_deficit represents the number of unmatched closing brackets that need to be swapped with future opening brackets. Since each swap fixes two brackets, the minimum number of swaps required is (max_deficit + 1) // 2.

Why it works: The balance counter maintains the invariant that at any valid point, the number of opening brackets minus closing brackets should be non-negative. Any time the balance drops below zero, it identifies an unmatched closing bracket. The maximum deficit thus represents the worst imbalance and directly corresponds to the minimum swaps needed to correct the string. The problem gives us a string consisting only of opening brackets '[' and closing brackets ']'. The length of the string is always even, and the number of opening and closing brackets is guaranteed to be equal.

Our goal is to make the string balanced using the minimum number of swaps. A swap can occur between any two indices, not necessarily adjacent indices. This is important because swapping distant characters in one operation makes the problem much easier than adjacent-swap variants.

A balanced bracket string follows the same rules as valid parentheses expressions. Every opening bracket must eventually be matched with a closing bracket, and at no point while scanning from left to right should the number of closing brackets exceed the number of opening brackets.

For example:

• "[]" is balanced
• "[[]]" is balanced
• "[][]" is balanced
• "][][" is not balanced because it starts with a closing bracket

The output should be the minimum number of swaps needed to transform the string into any valid balanced arrangement.

The constraints are especially important:

• The length can be as large as 10^6
• This immediately rules out expensive simulations or repeated string reconstruction
• We need an algorithm with linear time complexity
• Memory usage should ideally be constant or very small

The problem also guarantees:

• The string length is even
• The number of '[' equals the number of ']'

This guarantee means a balanced arrangement is always possible.

Several edge cases are important:

• The string may already be balanced
• The string may begin with many consecutive closing brackets
• The string may alternate between valid and invalid states
• Extremely large inputs require an efficient one-pass solution

A naive implementation that repeatedly searches for swap positions or physically performs swaps on large strings could become too slow.

Approaches

Brute Force Approach

A brute-force solution would simulate the balancing process directly.

Whenever we encounter an invalid state, meaning the number of closing brackets exceeds the number of opening brackets, we could search forward for the next '[' character and swap it into the current position.

This approach works because every invalid prefix must eventually be repaired by bringing an opening bracket earlier into the string.

However, the implementation is inefficient because each correction may require scanning far ahead in the string to locate the next available '['. In the worst case, this repeated searching leads to quadratic time complexity.

For example, in a string like:

]]]]....[[[[

each repair operation may scan almost the entire remaining string.

Since n can reach 10^6, an O(n^2) solution is far too slow.

Optimal Greedy Observation

The key insight is that we do not actually need to perform the swaps.

Instead, we only need to count how many times the string becomes invalid while scanning from left to right.

We maintain a balance counter:

• '[' increases balance
• ']' decreases balance

If balance becomes negative, it means we have more closing brackets than opening brackets so far. This prefix cannot be balanced without a swap.

At that moment:

• One swap is required
• After the swap, the balance effectively becomes 1

Why 1?

Because swapping in an opening bracket changes the invalid prefix into a valid one with one unmatched opening bracket remaining.

This greedy observation allows us to compute the answer in a single pass without physically swapping characters.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly searches for future opening brackets and performs swaps
Optimal	O(n)	O(1)	Greedily tracks imbalance count without performing actual swaps

Algorithm Walkthrough

Optimal Greedy Algorithm

1. Initialize two variables:

• balance = 0
• swaps = 0

The balance variable represents how many unmatched opening brackets currently exist. 2. Traverse the string from left to right. 3. If the current character is '[', increment balance.

This means we have one more available opening bracket. 4. If the current character is ']', decrement balance.

This closing bracket attempts to match a previous opening bracket. 5. After updating the balance, check whether balance < 0.

A negative balance means we encountered more closing brackets than opening brackets in the current prefix. This prefix is invalid and must be repaired using a swap. 6. When balance < 0:

1. Increment swaps
2. Reset balance = 1

This simulates swapping the current ']' with some future '['.

After the swap:

• The current position becomes '['
• We effectively gain one unmatched opening bracket

7. Continue processing the rest of the string.
8. After the traversal completes, return swaps.

Why it works

The invariant is that balance always represents the number of unmatched opening brackets after applying the minimum swaps necessary so far.

Whenever balance becomes negative, the current prefix cannot possibly be balanced without introducing an opening bracket earlier in the string. A single swap with a future '[' is always sufficient to repair that invalid prefix.

Because we only perform swaps when absolutely necessary, and each negative balance requires at least one swap, the greedy strategy is optimal.

Python Solution

class Solution:
    def minSwaps(self, s: str) -> int:
        balance = 0
        max_deficit = 0
        
        for c in s:
            if c == '[':
                balance += 1
            else:  # c == ']'
                balance -= 1
            if balance < 0:
                max_deficit = max(max_deficit, -balance)
        
        return (max_deficit + 1) // 2

In this implementation, we iterate through the string while maintaining a running balance. Each time the balance goes negative, we record the maximum deficit. The final step divides the maximum deficit by 2 and rounds up, because each swap can fix two brackets in one operation. swaps = 0

    for char in s:
        if char == '[':
            balance += 1
        else:
            balance -= 1

        if balance < 0:
            swaps += 1
            balance = 1

    return swaps

The implementation follows the greedy algorithm directly.

The `balance` variable tracks the current bracket validity state while scanning the string.

When we see an opening bracket, we increase balance because it can potentially match a future closing bracket.

When we see a closing bracket, we decrease balance because it consumes one unmatched opening bracket.

The important logic occurs when `balance < 0`. This indicates an invalid prefix. At that moment:

- We count one swap
- We reset balance to `1`

This reset simulates bringing a future `'['` into the current position.

The algorithm never physically swaps characters because the exact swap locations do not matter. Only the number of required corrections matters.

Since the string is traversed exactly once and only constant extra memory is used, the solution is highly efficient.

## Go Solution

```go
func minSwaps(s string) int {
    balance := 0
    maxDeficit := 0
    
    for _, c := range s {
        if c == '[' {
    swaps := 0

    for _, char := range s {
        if char == '[' {
            balance++
        } else {
            balance--
        }
        if balance < 0 {
            if -balance > maxDeficit {
                maxDeficit = -balance
            }
        }
    }
    
    return (maxDeficit + 1) / 2
}

The Go version follows the same logic. The difference is in how strings are iterated: using a for _, c := range s loop ensures we handle each character as a rune. Go does not require explicit type conversions here because balance and maxDeficit are integers.

Worked Examples

Example 1: s = "][]["

Index	Char	Balance	Max Deficit
0	]	-1	1
1	[	0	1
2	]	-1	1
3	[	0	1

max_deficit = 1 → minimum swaps = (1 + 1) // 2 = 1.

Example 2: s = "]]][[["

Index	Char	Balance	Max Deficit
0	]	-1	1
1	]	-2	2
2	]	-3	3
3	[	-2	3
4	[	-1	3
5	[	0	3

max_deficit = 3 → minimum swaps = (3 + 1) // 2 = 2.

Example 3: s = "[]"

Index	Char	Balance	Max Deficit
0	[	1	0
1	]	0	0

max_deficit = 0 → minimum swaps = 0.

    if balance < 0 {
        swaps++
        balance = 1
    }
}

return swaps

}

The Go implementation is nearly identical to the Python version.

A few Go-specific details are worth noting:

- Strings in Go are immutable, but we never modify the string anyway
- The loop iterates over runes using `range`
- Integer overflow is not a concern because the maximum string length is only `10^6`
- No additional slices or stacks are needed, which keeps memory usage constant

## Worked Examples

### Example 1

Input: s = "][]["

| Index | Character | Balance Before | Balance After | Swaps |
| --- | --- | --- | --- | --- |
| 0 | ] | 0 | -1 → reset to 1 | 1 |
| 1 | [ | 1 | 2 | 1 |
| 2 | ] | 2 | 1 | 1 |
| 3 | [ | 1 | 2 | 1 |

Final answer:

1

### Example 2

Input: s = "]]][[["

| Index | Character | Balance Before | Balance After | Swaps |
| --- | --- | --- | --- | --- |
| 0 | ] | 0 | -1 → reset to 1 | 1 |
| 1 | ] | 1 | 0 | 1 |
| 2 | ] | 0 | -1 → reset to 1 | 2 |
| 3 | [ | 1 | 2 | 2 |
| 4 | [ | 2 | 3 | 2 |
| 5 | [ | 3 | 4 | 2 |

Final answer:

2

### Example 3

Input: s = "[]"

| Index | Character | Balance Before | Balance After | Swaps |
| --- | --- | --- | --- | --- |
| 0 | [ | 0 | 1 | 0 |
| 1 | ] | 1 | 0 | 0 |

Final answer:

0

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | We iterate through the string once, performing constant work per character. |
| Space | O(1) | Only a few integer variables are used, independent of input size. |

The algorithm is extremely efficient, even for the upper bound of `n = 10^6`, since it does not require extra storage or nested iterations.
| Time | O(n) | The string is scanned exactly once |
| Space | O(1) | Only a few integer variables are used |

The algorithm performs constant work for each character in the string. No nested loops, stacks, or auxiliary arrays are required.

Because the implementation avoids physically performing swaps, memory usage remains constant regardless of input size.

## Test Cases

Provided examples

assert Solution().minSwaps("][][") == 1 # one swap needed assert Solution().minSwaps("]]][[[") == 2 # two swaps needed assert Solution().minSwaps("[]") == 0 # already balanced

Additional cases

assert Solution().minSwaps("[][][][]") == 0 # already balanced, alternating assert Solution().minSwaps("[[]][]") == 0 # balanced but nested assert Solution().minSwaps("]][[") == 1 # small reverse, one swap assert Solution().minSwaps("]]]][[[[") == 2 # multiple swaps needed assert Solution().minSwaps("[][" * 500000) == 0 # large balanced input assert Solution().minSwaps("][" * 500000) == 500000 # large unbalanced input

| Test | Why |
| --- | --- |
| `'][]['` | Single swap needed to balance |
| `']]][[['` | Multiple swaps required, checks cumulative deficit |
| `'[]'` | Already balanced, simplest case |
| `'[][][][]'` | Already balanced with nested pattern |
| `'[['*n + ']]'*n` | Tests large input scalability |

## Edge Cases

**1. Already balanced string**: Strings like `"[]"` or `"[][]"` require zero swaps. The algorithm correctly handles this by never letting `balance` go negative, so `max_deficit` remains zero.

**2. Fully reversed string**: Strings like `"]["` or `"]]][[["` produce maximum initial deficits. Our algorithm accurately tracks `max_deficit` and calculates the exact number of swaps needed.

**3. Large input**: For `n = 10^6`, the algorithm avoids using extra data structures and operates in linear time with constant space. This ensures it handles extreme cases efficiently without memory overflow or timeouts.

This method is robust, handles edge cases, and scales linearly with input size.
sol = Solution()

# Provided examples
assert sol.minSwaps("][][") == 1          # Single swap needed
assert sol.minSwaps("]]][[[") == 2        # Multiple corrections required
assert sol.minSwaps("[]") == 0            # Already balanced

# Small edge cases
assert sol.minSwaps("][") == 1            # Smallest invalid input
assert sol.minSwaps("[[]]") == 0          # Nested balanced brackets
assert sol.minSwaps("[][]") == 0          # Sequential balanced brackets

# Consecutive invalid prefixes
assert sol.minSwaps("]]][[[") == 2        # Heavy imbalance at start
assert sol.minSwaps("]]]][[[[") == 2      # Larger imbalance pattern

# Alternating imbalance
assert sol.minSwaps("][][[]") == 1        # One early correction

# Large balanced case
assert sol.minSwaps("[" * 500 + "]" * 500) == 0  # Already valid

# Large worst-case style input
assert sol.minSwaps("]" * 500 + "[" * 500) == 250  # Maximum imbalance pattern

Test Case Summary

Test	Why
"[]”	Verifies already balanced input
"]["	Smallest invalid case
"][]["	Tests single required swap
"]]][[["	Tests multiple imbalance repairs
"[[]]"	Tests nested balanced structure
"[][]"	Tests sequential balanced structure
"]]]][[[["	Tests larger imbalance prefix
"][][[]"	Tests mixed valid and invalid regions
"[" * 500 + "]" * 500	Tests large already-balanced input
"]" * 500 + "[" * 500	Tests worst-case imbalance pattern

Edge Cases

Already Balanced Strings

Inputs such as:

"[]"
"[[]]"
"[][]"

never cause the balance to become negative.

A buggy implementation might still attempt unnecessary swaps or miscount balance transitions. This implementation correctly returns 0 because the balance < 0 condition is never triggered.

Strings Starting with Many Closing Brackets

Inputs like:

"]]][[["

are particularly dangerous because the balance immediately becomes negative.

A naive implementation might incorrectly reset balance to 0 after a swap. However, after swapping in an opening bracket, one unmatched opening bracket should remain, so the correct reset value is 1.

This implementation handles that correctly.

Extremely Large Inputs

The constraint allows strings up to 10^6 characters.

Any implementation that repeatedly searches ahead, constructs new strings, or physically performs swaps may time out or consume too much memory.

This implementation processes the string in one pass with constant extra memory, making it efficient even for the largest valid inputs.