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:

  1. Initialize a variable ans to zero. This variable will track the number of unpaired opening brackets as the code iterates through the string.

  2. Iterate through each character c in the string s:

    • If c is an opening bracket '[', increment ans. This is because each opening bracket could potentially require a closing bracket to balance it out.
    • Else if c is a closing bracket ']' and ans is greater than zero, it means there's an unpaired opening bracket available, so decrement ans. This represents pairing the closing bracket with an earlier opening bracket that was unmatched.
  3. 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 of ans), ensuring a correct count of swaps for balancing the string.

  4. 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 Evaluator

Example 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:

  1. Initialize ans as 0.

  2. Start iterating over each character in the string:

    • For the first character ], since ans 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 [, increase ans to 1 (one unpaired opening bracket).
    • For the fifth character [, increase ans to 2 (two unpaired opening brackets).
    • For the sixth character [, increase ans to 3 (three unpaired opening brackets).
  3. After iterating, ans is 3, representing three unpaired opening brackets.

  4. To calculate the minimum number of swaps, we apply (ans + 1) >> 1, which is (3 + 1) >> 1 equals 4 >> 1 which is 2.

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Depth first search is equivalent to which of the tree traversal order?


Recommended Readings