Vultr DocsLatest Content

Minimum Number of Swaps to Make the String Balanced

Updated on 19 June, 2025
Minimum Number of Swaps to Make the String Balanced header image

Problem Statement

Given a zero-indexed string s of even length n, containing exactly half opening brackets '[' and half closing brackets ']', the task is to make the string balanced using the minimum number of bracket swaps. A string is considered balanced if it can be represented as an empty string, as a concatenation AB where both A and B are balanced strings, or as a bracketed sequence [C] where C is a balanced string. The swaps can be performed between any two indices multiple times to achieve a balanced configuration.

Examples

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

Approach and Intuition

To determine the minimum swaps needed to balance the string, consider the following:

  1. Identify Imbalance:

    • Traverse the string while maintaining a counter to track the balance of brackets.
    • Increment the counter for an opening bracket [ and decrement for a closing bracket ].
    • A negative balance at any point indicates more closing brackets before corresponding opening ones, contributing to imbalance.

  2. Count Required Swaps:

    • Keep a running total of how many opening brackets are needed (when balance is negative), which corresponds directly to the number of swaps needed.
    • For each negative balance value (indicating an imbalance where there are too many ']' before '['), you'd potentially prepare for a swap.

  3. Detailed Parsing for Swaps:

    • Start with the leftmost character and move right, adjusting the count of required opening brackets as you parse through each character.
    • Whenever you encounter more [ than needed or an excess ] out of place, that suggests potential swap candidates.

  4. Calculate Minimum Swaps:

    • As you track and adjust mismatches during your single pass from the left to the right of the string, sum up the needed swaps. This approach ensures that you're always making optimal decisions, minimizing unnecessary swaps.

Example Insights:

  • Example 1: s = "][]["

    • Initially, the string starts with an imbalance (] without any preceding [), requiring one swap to balance.
    • A swap between the first ] and the last [ resolves the issue.

  • Example 2: s = "]]][[["

    • Start with a severe imbalance of three sequential ]. This configuration needs a series of swaps, each time pairing an unbalanced ] with a later [.

  • Example 3: s = "[]"

    • The string is already balanced, demonstrating the case with zero swaps.

The approach leverages the lineage of balance tracking in a single scan, counting mismatches, and then translating these mismatches into swap operations. This straightforward yet efficient method ensures the minimum number of swaps are performed to achieve a balanced string.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    int minimumSwaps(string str) {
        int openCount = 0;
        int length = str.length();
    
        for (int i = 0; i < length; i++) {
            if (str[i] == '[')
                openCount++;
            else {
                if (openCount > 0) openCount--;
            }
        }
        return (openCount + 1) / 2;
    }
};

In the solution for the problem of determining the minimum number of swaps needed to balance a string that can contain brackets such as [ and ], the C++ code efficiently calculates the result using a straightforward counting method.

  • First, the function minimumSwaps initializes openCount to zero to keep track of unbalanced [ characters.
  • As the function iterates over each character in the string, it increments the openCount each time an [ is encountered. If a ] is encountered and there is an unmatched [ (openCount > 0), it decrements the openCount.
  • After looping through all the characters, the number of swaps needed to balance the string is calculated by taking half of the remaining openCount. This is based on the understanding that each swap can fix two misplacements.
  • The final result is returned using (openCount + 1) / 2. This expression ensures that any leftover misplacement after halving the count is rounded up, accurately accounting for the need of an additional swap if there’s an odd number of misplacements.

By using this simple counting framework, the program effectively identifies and corrects imbalances in the string with minimal operations.

java 
class Solution {
    
    public int minimumSwapsToBalance(String brackets) {
        int openCount = 0;
        for (int index = 0; index < brackets.length(); index++) {
            char currentBracket = brackets.charAt(index);
            if (currentBracket == '[') openCount++;
            else {
                if (openCount > 0) openCount--;
            }
        }
        return (openCount + 1) / 2;
    }
}

This program is designed to determine the minimum number of swaps needed to balance a string of brackets in Java. The function minimumSwapsToBalance takes a single string, brackets, as an argument, consisting solely of '[' and ']' characters.

  • The function initializes an openCount variable to track the unbalanced open brackets ('[').
  • Iterate through each character in the string. For each:
    • If the character is '[', increment openCount.
    • If the character is ']', and there's an unbalanced '[' (i.e., openCount > 0), decrement openCount to represent a pairing.
  • After the loop, any remaining unpaired '[' indicates an imbalance. The minimum swaps needed is half of the remaining openCount, rounded up, since each swap fixes two imbalances. This result is calculated by (openCount + 1) / 2.

This approach effectively counts how many open brackets remain unbalanced and computes the number of swaps needed to pair them up with closing brackets, ensuring the string becomes balanced with the minimum operations.

python 
class Solution:
    def minimumSwaps(self, brackets: str) -> int:
        count_brackets = 0
        for char in brackets:
            if char == "[":
                count_brackets += 1
            elif count_brackets > 0:
                count_brackets -= 1
        return (count_brackets + 1) // 2

The problem of determining the minimum number of swaps to make a string of brackets balanced involves analyzing a sequence of '[' and ']' characters to rearrange mismatches appropriately. The provided Python solution executes this by iterating over the string and maintaining a counter to track the number of unbalanced opening brackets, denoted by '['.

  • Initially, set the counter count_brackets to zero.
  • Traverse through each character in the input string:
    • Increment the count_brackets if the current character is '['.
    • If the character is ']' and count_brackets is greater than 0 (indicating there was a previous unmatched '['), decrement the count_brackets.
  • The absolute number of unmatched '[' characters is stored in count_brackets after processing the entire string.
  • The formula (count_brackets + 1) // 2 effectively computes the minimum swaps needed. This calculation works by assuming each swap can fix two unmatched brackets.
  • Return the result of the calculation as the minimum number of swaps required to balance the string.

Ensure this approach is implemented for strings composed specifically of '[' and ']' characters to determine balancing swaps accurately.

Comments

No comments yet.