Minimum Number of Swaps to Make the String Balanced

LeetCode 2095 | Difficulty: Medium

Medium

Problem Description

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.

Example 1:

Input: s = "][]["
Output: 1
Explanation: You can make the string balanced by swapping index 0 with index 3.
The resulting string is "[[]]".

Example 2:

Input: s = "]]][[["
Output: 2
Explanation: 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
Explanation: The string is already balanced.

Constraints:

- `n == s.length`

- `2 <= n <= 10^6`

- `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`.

Topics: Two Pointers, String, Stack, Greedy

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

---

Solutions

Solution 1: C# (Best: 116 ms)

Metric	Value
Runtime	116 ms
Memory	68.4 MB
Date	2022-01-21

Solution

public class Solution {
    public int MinSwaps(string s) {
       int size = 0;
       for(int i=0;i<s.Length;i++)
       {
           if(s[i] == '[')
           {
               size++;
           }
           else
           {
               if(size>0) size--;
           }
       }
        return (size+1)/2;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Iterate over the string and keep track of the number of opening and closing brackets on each step.

Hint 2: If the number of closing brackets is ever larger, you need to make a swap.

Hint 3: Swap it with the opening bracket closest to the end of s.