
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
'['
equalsn / 2
, and the number of closing brackets']'
equalsn / 2
.
Approach and Intuition
To determine the minimum swaps needed to balance the string, consider the following:
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.
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.
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.
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.
- Initially, the string starts with an imbalance (
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[
.
- Start with a severe imbalance of three sequential
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
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
initializesopenCount
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 theopenCount
. - 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.
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), decrementopenCount
to represent a pairing.
- If the character is '[', increment
- 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.
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 thecount_brackets
.
- Increment the
- 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.
No comments yet.