• Posts

Problem 1963 Minimum Number of Swaps to Make the String Balanced

Problem Statement

Link - Problem 1963

Question

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:

• It is the empty string, or
• It can be written as AB, where both A and B are balanced strings, or
• It can be written as [C], where C is a balanced string.

You may swap the brackets at any two indices any number of times.

Return the minimum number of swaps to make s balanced.

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.

Solution

class Solution {
public:
    int minSwaps(string s) {
        stack<char> st;
        int unbalanced = 0;
        for (int i = 0; i < s.size(); i++) {
            char ch = s[i];
            if (ch == '[')
                st.push(ch);
            else {
                if (!st.empty()) st.pop();
                else
                    unbalanced++;
            }
        }
        // we do (unbalanceed+1)/2 becauze we are removing all the balanced pairs using st and
        // whatever non-balanced count is remaining is to be paired , thats why /2 is done
        // 1 is added to do ceil(unbalanced/2) thats all
        return (unbalanced + 1) / 2;
    }
};

Complexity Analysis

| Algorithm             | Time Complexity | Space Complexity |
| --------------------- | --------------- | ---------------- |
| Stack-based iteration | O(n)            | O(n)             |

Explanation

Intial Thoughts

To solve this problem, consider a string as a series of opening and closing brackets. Think of balancing a string like building a tower with blocks, where each opening bracket is like adding a block and each closing bracket is like removing a block. The tower is balanced if at every step, the number of blocks added is greater than or equal to the number of blocks removed. Consider the process of examining the string from left to right, keeping track of the balance between opening and closing brackets encountered so far. Think of how a stack can be used to track this balance. Note that a swap can only happen between two different types of brackets, and consider how the process can be simplified by focusing on the minimum number of swaps needed. Consider how to handle cases where there are more closing brackets than opening brackets in the initial part of the string. Think about the strategy of always trying to balance the string as soon as possible, which may involve swapping a closing bracket with an opening bracket that appears later in the string.

Intuitive Analysis

Intuitively, the solution involves recognizing that to balance a string, each opening bracket must be paired with a closing bracket. Analyze how using a stack can help track the balance of opening and closing brackets. Consider how each time a closing bracket is encountered when the stack is empty, it means there is an unbalanced closing bracket that needs to be swapped with a later opening bracket. Think about how counting these unbalanced closing brackets and then dividing by 2 gives the minimum number of swaps needed, because each swap can balance two brackets. Realize that adding 1 before dividing by 2 is a way to perform a ceiling function, ensuring that if there is an odd number of unbalanced closing brackets, the result is still rounded up to the nearest whole number. Consider how this approach works because it effectively removes all the balanced pairs using the stack and whatever unbalanced count is remaining is to be paired, thus requiring the division by 2.

1. Intuition

• The problem requires finding the minimum number of swaps to make a string of brackets balanced.
• A string is balanced if it can be divided into smaller balanced strings or if it is enclosed in a pair of brackets.
• The key insight is to count the number of unbalanced closing brackets, which will determine the minimum number of swaps required.
• The number of unbalanced closing brackets can be calculated by iterating through the string and using a stack to keep track of the opening brackets.
• If a closing bracket is encountered when the stack is empty, it means that there is no corresponding opening bracket, so the count of unbalanced closing brackets is incremented.
• The minimum number of swaps required is then calculated as the ceiling of half the number of unbalanced closing brackets.
• This approach works because each swap can balance two unbalanced brackets, so the minimum number of swaps is proportional to the number of unbalanced brackets.

2. Implementation

• The solution uses a stack to keep track of the opening brackets encountered so far.
• The unbalanced variable is used to count the number of unbalanced closing brackets.
• The code iterates through the string using a for loop, and for each character, it checks if it is an opening bracket using if (ch == '['), in which case it pushes the character onto the stack.
• If the character is a closing bracket, it checks if the stack is empty using if (!st.empty()), and if it is not empty, it pops the corresponding opening bracket from the stack.
• If the stack is empty when a closing bracket is encountered, it increments the unbalanced count.
• Finally, the code returns the minimum number of swaps required using the formula (unbalanced + 1) / 2, which calculates the ceiling of half the number of unbalanced closing brackets.
• The use of (unbalanced + 1) / 2 ensures that the result is rounded up to the nearest integer, which is necessary because each swap can balance two unbalanced brackets.

Complexity Analysis

Time Complexity:

• The algorithm iterates over the string s once using a for loop, which results in a linear time complexity of O(n), where n is the length of the string.
• The dominant operation is the iteration over the string s, and the push and pop operations on the stack st are performed at most n times.
• The time complexity is O(n) because the algorithm performs a constant amount of work for each character in the string, resulting in a linear relationship between the input size and the time taken.

Space Complexity:

• The algorithm uses a stack st to keep track of the opening brackets, which in the worst-case scenario can grow up to a size of n, where n is the length of the string.
• The space complexity is dominated by the stack st, which can store up to n elements in the worst case.
• The space complexity is O(n) because the algorithm uses a data structure that scales linearly with the input size, resulting in a linear relationship between the input size and the memory used.

Footnote

This question is rated as Medium difficulty.

Hints

Iterate over the string and keep track of the number of opening and closing brackets on each step.

If the number of closing brackets is ever larger, you need to make a swap.

Swap it with the opening bracket closest to the end of s.

Similar Questions: