We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Swaps to Make the String Balanced

Difficulty: Medium

Problem Description

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 it can be formed according to specific rules regarding the arrangement of brackets. You may swap the brackets at any two indices any number of times. Return the minimum number of swaps to make s balanced.

Key Insights

  • The string must have equal numbers of opening and closing brackets, which it does by definition.
  • To determine how many swaps are needed, we can track the balance of brackets as we iterate through the string.
  • A negative balance indicates an excess of closing brackets, which can be corrected by swapping.
  • The number of swaps needed correlates to how deep the balance goes into negative values.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves iterating through the string to maintain a balance counter. We increment the counter for an opening bracket '[' and decrement it for a closing bracket ']'. Whenever the balance goes negative, it indicates that there are more closing brackets than opening brackets up to that point. The absolute value of the lowest balance reached gives the number of unmatched closing brackets, which directly corresponds to the number of swaps needed (divided by 2, since each swap fixes two unmatched brackets).

Code Solutions

def minSwaps(s: str) -> int:
    balance = 0
    min_balance = 0
    
    for char in s:
        if char == '[':
            balance += 1
        else:
            balance -= 1
        min_balance = min(min_balance, balance)
        
    return (abs(min_balance) + 1) // 2
← Back to All Questions