How to Solve Minimum Number of Swaps to Make the String Balanced

To solve this problem, iterate through the string while tracking the current imbalance of brackets. Each time the imbalance is negative, a swap is required to maintain balance. Using a two-pointer or counter-based approach ensures O(n) time and O(1) space efficiency while handling large strings with equal numbers of '[' and ']'.

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

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.

How GhostInterview Helps

• Automatically identifies imbalance points and calculates the minimum swaps needed with one-pass scanning.
• Highlights exact positions requiring swaps without manual simulation of each move.
• Provides a stepwise greedy solution tied to the two-pointer pattern, ensuring O(n) time and O(1) space.

Topic Pages

• Two Pointers
• String
• Stack
• Greedy

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.