Problem of The Day: Minimum Number of Swaps to Make the String Balanced

Problem Statement

Intuition

The problem asks us to find the minimum number of swaps required to make a string of brackets balanced. If we observe the brackets carefully, every closing bracket ] must have a corresponding opening bracket [ before it. So, an imbalance happens when a ] occurs before [ in a string. The approach involves counting and correcting this imbalance efficiently by swapping brackets.

Approach

1. Balancing with a stack:

   • We iterate through the string and use a stack to track unbalanced brackets. Whenever we find an unmatched [ followed by ], we pop from the stack to cancel out a pair. If we encounter ] without a matching [, we push it onto the stack.
   • By the end of this iteration, the stack will contain only unmatched brackets, either as excess [ or ].

2. Swapping:

   • Once we know the imbalance, we need to swap the ] brackets that are in the wrong positions with [ that are on the opposite side of the string.
   • We maintain two pointers (l and r), moving from left to right and right to left respectively, and whenever we find an imbalance (] at position l and [ at position r), we swap them and count the swap.
   • The process is repeated until all imbalanced brackets are swapped.

Complexity

• Time complexity:
  • The first pass through the string takes \(O(n)\) time where n is the length of the string.
  • The second pass to swap the characters also takes \(O(n)\). Thus, the overall time complexity is \(O(n)\).
• Space complexity:
  • We use a stack that can at most hold all the unmatched brackets. Therefore, the space complexity is \(O(n)\).

Code

class Solution:
    def minSwaps(self, s: str) -> int:
        stack = []
        for c in s:
            if stack and stack[-1] == '[' and c == ']':
                stack.pop()
            else:
                stack.append(c)
        s = ''.join(stack)
        l, r = 0, len(s) - 1
        res = 0
        while l < r:
            if s[l] == ']':
                while r >= 0 and s[r] == ']':
                    r -= 1
                s[l], s[r] == s[r], s[l]
                res += 1
            l += 2
            r -= 2
        return res

Editorial

Approach 1: Stack

class Solution:
    def minSwaps(self, s: str) -> int:
        stack = deque()
        unbalanced = 0
        for ch in s:
            # If an opening bracket is encountered, push it in the deque.
            if ch == "[":
                stack.append(ch)
            else:
                # If the deque is not empty, pop it.
                if stack:
                    stack.pop()
                # Otherwise increase the count of unbalanced brackets.
                else:
                    unbalanced += 1
        return (unbalanced + 1) // 2

Approach 2: Space-Optimized Stack

class Solution:
    def minSwaps(self, s: str) -> int:
        stack_size = 0
        for ch in s:
            # If character is opening bracket, increment the stack size.
            if ch == "[":
                stack_size += 1
            else:
                # If the character is closing bracket, and we have an opening bracket, decrease
                # the stack size.
                if stack_size > 0:
                    stack_size -= 1
        return (stack_size + 1) // 2