Minimum Number of Swaps to Make the String Balanced

Minimum Number of Swaps to Make the String Balanced - 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.

Input & Output

Example 1 — Basic Unbalanced Case

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

› Output: 2

💡 Note: We have 3 closing brackets followed by 3 opening brackets. Need 2 swaps: swap positions 0,3 and 1,4 to get "[[][]]" which is balanced.

Example 2 — Already Balanced

$ Input: s = "[]"

› Output: 0

💡 Note: String is already balanced with proper opening and closing bracket pairs, so no swaps needed.

Example 3 — Mixed Pattern

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

› Output: 1

💡 Note: Only 1 closing bracket is unmatched at the start. One swap between positions 0 and 3 gives "[]][][" which can be further balanced.

Constraints

2 ≤ s.length ≤ 10⁶
s.length is even
s consists of exactly s.length/2 opening brackets '[' and s.length/2 closing brackets ']'

Visualization

Tap to expand

Understanding the Visualization

Input

Unbalanced string with equal opening and closing brackets

Process

Track balance and identify unmatched closing brackets

Output

Minimum number of swaps needed

Key Takeaway

🎯 Key Insight: Each swap fixes exactly 2 unmatched brackets, so we need (unmatched + 1) / 2 swaps

Asked in

f Facebook 15 A Amazon 12 M Microsoft 8

The key insight is that each swap fixes exactly 2 unmatched brackets. By tracking the running balance and counting excess closing brackets, we can calculate the minimum swaps as (unmatched + 1) / 2. Best approach is greedy balance tracking. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Swaps	O(2^n)	O(n)	Try all possible swaps until string becomes balanced
Greedy - Count Unmatched Brackets	O(n)	O(1)	Track running balance and count excess closing brackets

Brute Force - Try All Swaps — Algorithm Steps

Step 1: Generate all possible ways to swap brackets
Step 2: For each combination, check if string is balanced
Step 3: Return minimum swaps among valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Swaps

Try swapping every pair of different brackets

Check Balance

Test if resulting string is balanced

Find Minimum

Return smallest number of swaps that work

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <limits.h>

int isBalanced(const char* str) {
    int count = 0;
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        if (str[i] == '[') {
            count++;
        } else {
            count--;
            if (count < 0) return 0;
        }
    }
    return count == 0;
}

int backtrack(char* str, int swaps) {
    if (isBalanced(str)) return swaps;
    
    int minSwaps = INT_MAX;
    int len = strlen(str);
    
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (str[i] != str[j]) {
                char temp = str[i];
                str[i] = str[j];
                str[j] = temp;
                
                int result = backtrack(str, swaps + 1);
                if (result < minSwaps) {
                    minSwaps = result;
                }
                
                temp = str[i];
                str[i] = str[j];
                str[j] = temp;
            }
        }
    }
    
    return minSwaps;
}

int solution(char* s) {
    return backtrack(s, 0);
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Need to try exponentially many swap combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Stack space for recursion and string copies

⚡ Linearithmic Space

46.1K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Swaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler