LeetCode: Minimum Number of Swaps to Make the String Balanced

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 "[[][]]".        

Solution:

Approach:

1. Use a stack to keep track of unmatched opening brackets.
2. Traverse through the string:If the stack is empty and a closing bracket ] is encountered, increment the count of invalid closing brackets (invalid).If a closing bracket ] is encountered but there is an unmatched opening bracket [, pop it from the stack (valid pair found).If an opening bracket [ is encountered, push it onto the stack.
3. Finally, the number of swaps needed is the ceiling of half the invalid closing brackets, as two invalid brackets require one swap to correct.

Complexity:

• Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
• Space Complexity: O(n / 2), in the worst case, if all the opening bracket are found in the start of the string.

Variable Description:

• stack: A list that stores unmatched opening brackets ([).
• invalid: An integer that tracks the number of unmatched closing brackets (]).
• s: The current character in the string during iteration.

import math 
class Solution: 
    def minSwaps(self, string: str) -> int: 
        stack = []
        invalid = 0 
        for s in string: 
            if not stack and s == "]": 
                invalid += 1 
            elif stack and s == "]": 
                stack.pop() 
            else: 
                stack.append(s) 
        return math.ceil(invalid / 2)        

??? Uncover a secret LeetCode trick in the comments! ????