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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Swaps to Make the String Balanced

Number: 2095

Difficulty: Medium

Paid? No

Companies: Microstrategy, Google, Amazon, Expedia, Meta, Nutanix, Twilio, PayPal

Problem Description

Given an even-length string s containing exactly n/2 opening brackets '[' and n/2 closing brackets ']', determine the minimum number of swaps required to make s balanced. A string is balanced if it is empty, or it can be decomposed into two balanced strings, or it can be written as "[C]" where C is balanced.

Key Insights

  • The challenge revolves around identifying imbalance during a single pass through the string.
  • Using a counter (balance) helps track the difference between opening and closing brackets.
  • When the counter goes negative, it indicates an excess of closing brackets, meaning a swap is needed.
  • Performing a swap effectively converts a problematic closing bracket into an opening bracket, hence resetting the local imbalance.
  • This greedy approach, processing the string from left to right, guarantees a minimal number of swaps.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string s.
Space Complexity: O(1) as only constant extra space is used.

Solution

The solution uses a greedy algorithm with a single pass through the string. A variable "balance" counts the net number of opening brackets. For each character:

  • If the character is '[', increment balance.
  • If the character is ']', decrement balance.
  • When balance becomes negative, it means that at that point there are more closing brackets than opening ones; hence, a swap is needed. Increase the swap counter and reset balance to 1 (simulating the swap where the closing bracket is effectively turned into an opening one). This approach efficiently computes the minimum swaps required.

Code Solutions

# Python solution with line-by-line comments

def minSwaps(s: str) -> int:
    balance = 0  # current net count of '[' minus ']'
    swaps = 0    # number of swaps required
    
    # Process each character in the string s
    for ch in s:
        if ch == '[':
            balance += 1  # increment balance for an opening bracket
        else:
            balance -= 1  # decrement balance for a closing bracket
        
        # If balance is negative, we have an extra closing bracket.
        if balance < 0:
            swaps += 1      # perform a swap (conceptually turning ']' into '[')
            balance = 1     # after swap, the balance is corrected
            
    return swaps

# Example usage:
s = "]]][[["
print(minSwaps(s))  # Output should be 2
← Back to All Questions