1963. Minimum Number of Swaps to Make the String Balanced
Problem Description
In this problem, you are presented with a string s
with an even length n
. The string contains exactly n / 2
opening brackets '[' and n / 2
closing brackets ']'. A balanced string is defined as:
- An empty string, or;
- A concatenation of two balanced strings
AB
, or; - A string that contains another balanced string within it enclosed by a pair of brackets
'[C]'
.
Your task is to determine the minimum number of swaps between any two indices needed to transform string s
into a balanced string. A swap means exchanging the characters at two specified indices in the string. You can perform any number of swaps.
Intuition
The intuition behind the solution is to track the imbalance of brackets at any point in the string. When traversing the string, keep a counter that increases when encountering an opening bracket '[' and decreases when encountering a closing bracket ']', as long as there was a previously unpaired opening bracket (i.e., the counter is positive). If the counter is zero, and a closing bracket is found, then this is an excess closing bracket that can potentially be swapped to balance a previous excess opening bracket.
Every time you encounter an excess closing bracket (signaled by the counter at zero before decrement), you know that at some point in the future, a swap will be needed to pair that closing bracket with a previous opening bracket.
Once the entire string has been traversed, the counter will have the total count of unpaired opening brackets. Since each swap can fix two unpaired brackets (by bringing an opening and a closing bracket together), the minimum number of swaps will be half of the total count of unpaired opening brackets.
The answer is the integer division of (ans + 1) >> 1
, which is equivalent to math.ceil(ans / 2)
. This takes care of both even and odd counts, as an odd count of unbalanced brackets will still require an extra swap. For example, if there are 3 unpaired opening brackets, you would need at least 2 swaps to make the string balanced.
Learn more about Stack, Greedy and Two Pointers patterns.
Solution Approach
The implementation of the solution is straightforward, using a simple counter to keep track of bracket balance. No additional data structures are necessary, and the solution employs a greedy approach. The code iterates over the string character by character, following these steps:
-
Initialize a variable
ans
to zero. This variable will track the number of unpaired opening brackets as the code iterates through the string. -
Iterate through each character
c
in the strings
:- If
c
is an opening bracket '[
', incrementans
. This is because each opening bracket could potentially require a closing bracket to balance it out. - Else if
c
is a closing bracket ']
' andans
is greater than zero, it means there's an unpaired opening bracket available, so decrementans
. This represents pairing the closing bracket with an earlier opening bracket that was unmatched.
- If
-
After the loop,
ans
will represent the total count of excess opening brackets, which are unpaired. Since each swap can balance two unpaired brackets, the minimum number of swaps required is(ans + 1) >> 1
. This right shift operation is equivalent to a floor division by two and then a ceiling operation on the result (for odd numbers ofans
), ensuring a correct count of swaps for balancing the string. -
Return the calculated number of swaps.
In essence, the algorithm is keeping track of how "deep" into unbalanced territory the string has gone with respect to opening brackets, and then using that depth to calculate the minimum number of swaps necessary to reintroduce balance.
Here is the implementation detail from the given solution:
1class Solution:
2 def minSwaps(self, s: str) -> int:
3 ans = 0
4 for c in s:
5 if c == '[':
6 ans += 1
7 elif ans:
8 ans -= 1
9 return (ans + 1) >> 1
It's noteworthy to mention that this implementation has a time complexity of O(n), where n is the length of the string. This is because it goes through the string once, performing constant time operations for each character.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Consider the string s = "]]][[["
. The string length n = 6
, with n / 2 = 3
opening brackets and n / 2 = 3
closing brackets.
Following the solution approach:
-
Initialize
ans
as 0. -
Start iterating over each character in the string:
- For the first character
]
, sinceans
is 0 (no unpaired opening brackets), do nothing. - For the second character
]
,ans
is still 0, do nothing. - For the third character
]
,ans
remains 0, do nothing. - For the fourth character
[
, increaseans
to 1 (one unpaired opening bracket). - For the fifth character
[
, increaseans
to 2 (two unpaired opening brackets). - For the sixth character
[
, increaseans
to 3 (three unpaired opening brackets).
- For the first character
-
After iterating,
ans
is 3, representing three unpaired opening brackets. -
To calculate the minimum number of swaps, we apply
(ans + 1) >> 1
, which is(3 + 1) >> 1
equals4 >> 1
which is2
.
Thus, it will take a minimum of 2 swaps to transform s
into a balanced string. One possible sequence of swaps:
- Swap indices 2 and 3 to form
][[[
(now the first pair is balanced). - Swap indices 4 and 5 to form
[][]
(all brackets are now balanced).
The implementation uses a simple counter to handle this tracking without additional data structures, which makes it efficient and easy to understand.
Solution Implementation
1class Solution:
2 def minSwaps(self, s: str) -> int:
3 imbalance = 0 # This variable tracks the number of imbalanced pairs
4
5 # Iterate through each character in the string
6 for c in s:
7 # If the character is an opening bracket, we increment imbalance
8 if c == '[':
9 imbalance += 1
10 # If the character is a closing bracket
11 elif imbalance:
12 # If there's an imbalance, we decrement it as the closing bracket balances an opening one
13 imbalance -= 1
14
15 # The minimum number of swaps is the number of unmatched open brackets divided by 2 (rounded up)
16 # because each swap can fix two imbalances.
17 return (imbalance + 1) // 2
18
1class Solution {
2
3 /**
4 * Calculates the minimum number of swaps to make the brackets sequence balanced.
5 *
6 * @param s Input string containing the brackets sequence.
7 * @return The minimum number of swaps required.
8 */
9 public int minSwaps(String s) {
10 int imbalance = 0; // This variable will keep the count of current imbalance
11 int swaps = 0; // This variable will keep the total number of swaps needed
12
13 // Iterate through each character in the input string
14 for (char bracket : s.toCharArray()) {
15 if (bracket == '[') {
16 // An opening bracket decreases the imbalance
17 imbalance++;
18 } else if (imbalance > 0) { // It's a closing bracket and we have an imbalance
19 // A closing bracket opposite to an opening one balances out,
20 // so decrease the current imbalance
21 imbalance--;
22 }
23 }
24
25 // The number of extra opening brackets is divided by 2 to get the number of swaps,
26 // because each swap will fix two misplaced brackets.
27 // If the number of imbalances is odd, it's divided by 2 and then rounded up.
28 // The rightward shift operation (imbalance + 1) >> 1 is effectively dividing by 2
29 // and rounding up in case of an odd number.
30 swaps = (imbalance + 1) >> 1;
31
32 return swaps;
33 }
34}
35
1class Solution {
2public:
3 int minSwaps(string s) {
4 int openBrackets = 0; // Variable to keep track of the number of unmatched '['
5 int swaps = 0; // Variable to keep track of the minimum number of swaps
6
7 // Loop through each character in the string
8 for (char& c : s) {
9 // If the current character is an opening bracket
10 if (c == '[') {
11 // Increase the count of unmatched opening brackets
12 openBrackets++;
13 }
14 // If it is a closing bracket and there are unmatched opening brackets
15 else if (openBrackets > 0) {
16 // Match the bracket and decrease the count of unmatched opening brackets
17 openBrackets--;
18 }
19 }
20
21 // The number of swaps needed is half the number of unmatched opening brackets (rounded up)
22 // because each swap can fix two unmatched opening brackets
23 swaps = (openBrackets + 1) / 2;
24
25 // Return the calculated number of swaps
26 return swaps;
27 }
28};
29
1// Function to calculate the minimum number of swaps required to balance the brackets
2function minSwaps(s: string): number {
3 let openBrackets: number = 0; // Variable to keep track of the number of unmatched '['
4 let swaps: number = 0; // Variable to keep track of the minimum number of swaps
5
6 // Loop through each character in the string
7 for (let c of s) {
8 // If the current character is an opening bracket
9 if (c === '[') {
10 // Increase the count of unmatched opening brackets
11 openBrackets++;
12 }
13 // If it is a closing bracket and there are unmatched opening brackets
14 else if (openBrackets > 0) {
15 // Match the bracket and decrease the count of unmatched opening brackets
16 openBrackets--;
17 }
18 // When an unmatched closing bracket is found and there are no open brackets to match
19 // it directly contributes to the number of swaps needed
20 }
21
22 // The number of swaps needed is half the number of unmatched opening brackets (rounded up)
23 // because each swap can fix two unmatched opening brackets
24 swaps = Math.ceil(openBrackets / 2);
25
26 // Return the calculated number of swaps
27 return swaps;
28}
29
Time and Space Complexity
Time Complexity
The time complexity of the function is O(n)
where n
is the length of the input string s
. This is because the function contains a single loop that iterates over each character in the input string exactly once to count the balance of brackets.
Space Complexity
The space complexity of the function is O(1)
. The only extra space used is for the variable ans
which keeps track of the net number of open brackets ('[') encountered during the loop. This does not depend on the input size, and thus, the space complexity is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview