Minimum Number Of Swaps To Make The String Balanced Leetcode [Python]

In this blog post, we'll tackle the Minimum Number Of Swaps To Make The String Balanced problem, which is a LeetCode problem #1963. This problem falls under the category of Arrays & Hashing and is considered to be of medium difficulty.

Companies like Facebook, Google, and Amazon have encountered similar problems, making it an interesting challenge for those aspiring to work in these tech giants.

Problem Overview

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.

Your task is to return the minimum number of swaps required to make the string 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:
1. Swap index 0 with index 4. s = "[]][][".
2. 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.

Efficient Python Code Solution

Here is a Python solution to the problem:

View on GitHub ➹

def minSwaps(self, s: str) -&gt; int:
    extraClose, maxClose = 0

    for c in s:
        if c == &quot;[&quot;:
            extraClose -= 1
        else:
            extraClose += 1

        maxClose = max(maxClose, extraClose)

    return (maxClose + 1) // 2  # Or math.ceil(maxClose / 2)

The code starts by initializing two variables, extraClose and maxClose, both set to 0. It then iterates through the characters of the input string s.

If a character is an opening bracket '[', it decrements extraClose by 1; otherwise, if it's a closing bracket ']', it increments extraClose by 1. The code also keeps track of the maximum value of extraClose seen so far in the variable maxClose.

Finally, it calculates the minimum number of swaps required by adding 1 to maxClose and performing integer division by 2. This solution works efficiently, as it ensures that the maximum number of extra closing brackets at any point is considered to minimize the number of swaps required.

Time and Space Complexity

The time complexity of this solution is O(n), where n is the length of the input string s.

This is because we perform a single pass through the string.

The space complexity is O(1), as we use a constant amount of additional memory to store the extraClose and maxClose variables.

Constraints Explained

The problem's constraints are as follows:

n == s.length: This constraint ensures that the length of the input string s is consistent with the value n.
2 <= n <= 106: The input string's length must be between 2 and 1,000,000, which is a large range of possible inputs.
n is even: This ensures that there is an equal number of opening and closing brackets in the string.
s[i] is either '[' or ']': The characters in the input string are limited to opening and closing brackets.

These constraints help define the problem space and the possible inputs that the solution should handle.

Edge Cases a Valid Solution Must Consider

When solving this problem, there are several edge cases that need to be considered:

Empty String: When the input string is empty, it is already balanced, so the minimum number of swaps required is 0.
String with No Swaps Needed: If the input string is already balanced, i.e., it satisfies the three criteria of a balanced string mentioned in the problem overview, then no swaps are needed, and the minimum number of swaps is 0.
String with Only Opening Brackets: If the input string contains only opening brackets, it cannot be balanced, and the minimum number of swaps is -1 to indicate that it's impossible to balance.
String with Only Closing Brackets: Similarly, if the input string contains only closing brackets, it cannot be balanced, and the minimum number of swaps is -1. These edge cases must be handled to ensure a robust and correct solution.

Reasoning Behind Our Approach

The approach used in the provided Python solution is efficient and clever.

It focuses on the key insight that each swap eliminates two extra closing brackets.

The code iterates through the input string and keeps track of the number of extra closing brackets using the extraClose variable.

When an opening bracket is encountered, it decrements extraClose by 1, and when a closing bracket is encountered, it increments extraClose by 1. The maxClose variable is updated to store the maximum value of extraClose seen so far.

The reason this works is that when we encounter a closing bracket, it can only match with an opening bracket that appears later in the string.

If we have extra closing brackets, we know that they cannot be matched with any opening brackets that have already appeared.

So, we keep track of this surplus of closing brackets.

To minimize the number of swaps, we need to reduce the number of extra closing brackets.

Swapping a closing bracket with an opening bracket eliminates two extra closing brackets.

Therefore, we take the maximum value of extraClose seen during the iteration, add 1 to account for the initial closing bracket, and then divide by 2 (perform integer division) to get the minimum number of swaps required to balance the string.

In this way, the code efficiently computes the answer in a single pass through the string without using any extra memory.

Conclusion

In this blog post, we've explored the Minimum Number Of Swaps To Make The String Balanced problem, which is a LeetCode problem #1963. We've provided a Python solution that efficiently calculates the minimum number of swaps required to balance the input string.

The approach is based on the observation that each swap eliminates two extra closing brackets.

It's important to handle edge cases such as empty strings and strings that are already balanced or impossible to balance.

Additionally, the problem's constraints define the input space and help ensure the solution's correctness and efficiency.

If you found this blog post helpful, please like and engage for more content.

If you have any questions, suggestions, or comments, feel free to share them below.

Your feedback is always appreciated, and it helps us improve our content.

For the full problem statement and to practice the solution, you can visit the LeetCode problem page.

Thank you for reading, and happy coding!