1963. Minimum Number of Swaps to Make the String Balanced - Detailed Explanation

Problem Statement

Description:
You are given a balanced bracket string s consisting only of the characters '[' and ']'. The string is guaranteed to have an equal number of '[' and ']' and its length is even. However, the string may not be “balanced” in the sense of valid bracket sequences. A string is balanced if for every prefix the number of '[' is greater than or equal to the number of ']'. In one swap, you can exchange any two characters in the string. Return the minimum number of swaps required to make the string balanced.

Examples:

1. Example 1:

   • Input: s = "[]"
   • Output: 0
   • Explanation: The string is already balanced.

2. Example 2:

   • Input: s = "][]["
   • Output: 1
   • Explanation:
     • Initial string: "][]["
     • Swap the first character ']' with the second character '[' to get "[][]", which is balanced.

3. Example 3:

   • Input: s = "]]][[["
   • Output: 2
   • Explanation:
     • Scan through the string: the worst imbalance (the maximum excess of closing brackets over opening brackets) is 3.
     • Since one swap can fix two imbalances, the minimum number of swaps is the ceiling of 3/2, which is 2.

Constraints:

• The length of s is even.
• s consists only of '[' and ']'.
• The total number of '[' equals the total number of ']'.

Hints Before the Solution

1. Greedy Observation:
   While scanning the string from left to right, maintain a counter (called “balance”) that increases by 1 for each '[' and decreases by 1 for each ']'. If at any point the balance becomes negative, it means there are more closing brackets than opening brackets up to that point, which indicates an imbalance.

2. Maximum Imbalance:
   The deepest (most negative) value reached by the balance during the scan indicates how many extra closing brackets have been encountered. Since swapping two characters can fix two mismatches, the number of swaps required is the ceiling of half the absolute value of the worst imbalance.

3. Avoid Simulation:
   Instead of simulating actual swaps, you can simply compute the worst imbalance and then derive the number of swaps mathematically.

Approaches

Approach 1: Greedy Balance Tracking (Optimal)

Idea:

• Iterate over the string while maintaining a balance counter:

  • Increment the counter for '[' and decrement for ']'.

• Track the minimum (most negative) value of the balance during the scan (let’s call it min_balance).

• The minimum number of swaps required is the ceiling of the absolute value of min_balance divided by 2.

  In integer arithmetic, this can be computed as:
  [ \text{swaps} = \frac{-\text{min\_balance} + 1}{2} ] (when using integer division, this formula effectively rounds up).

Why It Works:

• The most negative balance represents the maximum number of unmatched closing brackets before an opening bracket occurs.
• Each swap can fix two such imbalances, so you only need half as many swaps (rounded up).

Complexity:

• Time Complexity: O(n), where n is the length of the string (a single scan).
• Space Complexity: O(1) (only a few counters are used).

Approach 2: Brute Force Simulation (Not Recommended)

Idea:

• Simulate swapping characters until the string becomes balanced.
• Check after each swap if the string is valid.

Why Not Use:

• This approach is inefficient and complex, especially since a neat O(n) solution exists using the greedy method described above.

Code Implementations

Python Implementation