#1963

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Minimum Number of Swaps to Make the String Balanced

Determine the minimum swaps to balance a bracket string using two-pointer scanning with invariant tracking efficiently.

Problem Statement

Given a 0-indexed string s of even length n containing exactly n/2 opening brackets '[' and n/2 closing brackets ']', compute the minimum number of swaps required to make it balanced. A string is balanced if for every prefix of the string, the number of opening brackets is at least the number of closing brackets.

You may swap brackets at any two indices any number of times to achieve a balanced configuration. Return the minimum number of swaps needed to transform s into a balanced string.

Examples

Example 1

Input: s = "][]["

Output: 1

You can make the string balanced by swapping index 0 with index 3. The resulting string is "[[]]".

Example 2

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

Output: 2

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

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.

Solution Approach

Iterate with imbalance tracking

Traverse the string while maintaining a counter for the current balance. Increment for '[' and decrement for ']'. Whenever the counter drops below zero, increment the swap count and reset the counter, reflecting the need for a swap at that position.

Two-pointer greedy adjustment

Use two pointers or indices to locate mismatched brackets and swap when necessary. The left pointer moves forward through unbalanced ']', and the right pointer finds the next '[' to restore local balance efficiently without extra memory.

Constant space optimization

Instead of explicitly swapping characters, track the imbalance as a number. Every negative imbalance indicates a required swap. This reduces the space usage to O(1) while still counting the minimum swaps correctly.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each character is processed once during scanning. Space complexity is O(1) since only counters and a few variables are used, no extra arrays or stacks are required.

What Interviewers Usually Probe

Do you track the imbalance during iteration or attempt all swap combinations?
Can you optimize space by avoiding explicit swaps and using counters?
How do you determine the exact moment a swap is necessary in a single pass?

Common Pitfalls or Variants

Common pitfalls

Forgetting to reset the imbalance counter after each necessary swap, leading to incorrect totals.
Assuming swaps can be minimized by pairing only adjacent brackets rather than using imbalance tracking.
Using extra stacks or arrays unnecessarily, increasing space complexity beyond O(1).

Follow-up variants

Compute minimum swaps to balance strings with multiple types of brackets using a generalized two-pointer invariant.
Count the number of swaps required if only adjacent bracket swaps are allowed, requiring more careful tracking.
Determine maximum balanced prefix length after performing at most k swaps, applying similar imbalance tracking.

FAQ

What is the minimum number of swaps to make a string balanced?

It is the count of times the running imbalance of brackets drops below zero during a single pass through the string.

Can this problem be solved using a stack?

Yes, a stack can track unmatched brackets, but a counter for imbalance is more space-efficient for this exact problem.

Why does the two-pointer scanning pattern work here?

It efficiently locates mismatched brackets and determines swaps by tracking the running imbalance without extra storage.

What is the time and space complexity?

Time is O(n) as each character is processed once, and space is O(1) using only counters.

Does the string need to be preprocessed before applying the algorithm?

No preprocessing is needed; iterate directly while counting the imbalance and apply swaps virtually as required.

terminal

Solution

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$:

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#2000 reverse prefix of word #2030 smallest k length subsequence with occurrences of a letter #1850 minimum adjacent swaps to reach the kth smallest number