Problem Description

You are given a string s that contains an equal number of opening brackets '[' and closing brackets ']'. The string has even length n, with exactly n/2 opening brackets and n/2 closing brackets.

A string is considered balanced if it meets one of these conditions:

• It's an empty string
• It can be split into two parts AB where both A and B are balanced strings
• It has the form [C] where C is a balanced string

For example, "[]", "[[]]", and "[[][]]" are balanced, while "][][" and "][[[" are not balanced.

You can swap any two brackets in the string as many times as needed. Your task is to find the minimum number of swaps required to make the string balanced.

The key insight is that when traversing the string from left to right, we track unmatched opening brackets. When we encounter a closing bracket, we can match it with a previous unmatched opening bracket if one exists. After processing the entire string, any remaining unmatched brackets will form a pattern like "]]]...[[[..." where all closing brackets come before opening brackets.

To fix this pattern, we can swap brackets from opposite ends. Each swap eliminates 2 unmatched brackets, so if we have x unmatched opening brackets remaining, we need ⌊(x + 1) / 2⌋ swaps to balance the string.

Intuition

The key observation is that when we traverse the string from left to right, we can greedily match closing brackets with opening brackets we've seen so far. Think of it like a stack-based approach without actually using a stack - each '[' we encounter can potentially match with a future ']', and each ']' should match with the most recent unmatched '['.

As we scan through the string:

• When we see '[', we increment a counter (this bracket is waiting to be matched)
• When we see ']', if we have unmatched '[' available, we match them (decrement the counter)
• If we see ']' but have no unmatched '[', this ']' remains unmatched

After this process, all remaining unmatched brackets will naturally form a specific pattern: all the unmatched ']' will be at the beginning, and all the unmatched '[' will be at the end, giving us something like "]]]...[[[...".

Why does this pattern emerge? Because:

• Unmatched ']' brackets are those we encountered before seeing enough '[' brackets
• Unmatched '[' brackets are those left over after all possible matches were made

Now, to fix this pattern with minimum swaps, we can swap a ']' from the left portion with a '[' from the right portion. Each such swap fixes two pairs of brackets:

• The swapped '[' can now match with a ']' on its left
• The swapped ']' can now match with a '[' on its right

For example, if we have "]][[" and swap positions 1 and 2, we get "[][]", fixing both misplaced pairs with just one swap.

Therefore, if we have x unmatched '[' brackets (which equals the number of unmatched ']' brackets), we need ⌈x/2⌉ swaps, which can be written as (x + 1) >> 1 using bit manipulation.

Learn more about Stack, Greedy and Two Pointers patterns.

Solution Approach

The solution uses a greedy approach with a single counter variable to track unmatched brackets:

1. Initialize a counter: We use variable x to track the number of unmatched opening brackets '[' as we traverse the string.

2. Traverse the string: For each character c in the string:

   • If c == '[': Increment x by 1 (we found an opening bracket waiting to be matched)
   • If c == ']': Check if x > 0
     • If yes, decrement x by 1 (match this closing bracket with a previous opening bracket)
     • If no, this closing bracket remains unmatched (but we don't need to track it explicitly)

3. Calculate minimum swaps: After traversal, x represents the number of unmatched opening brackets. Since the string has equal numbers of '[' and ']', there are also x unmatched closing brackets at the beginning of the processed pattern.

   The formula for minimum swaps is ⌊(x + 1) / 2⌋, which in the code is implemented as (x + 1) >> 1 using right shift for integer division.

Why this works:

• The greedy matching ensures we minimize unmatched brackets
• After processing, we get a pattern like "]]]...[[[..." with x brackets of each type
• Each swap fixes 2 pairs of brackets
• We need ⌈x/2⌉ swaps, which equals ⌊(x + 1) / 2⌋

Example walkthrough: For string s = "]]][[["

• Start with x = 0
• ']': x = 0, remains unmatched
• ']': x = 0, remains unmatched
• ']': x = 0, remains unmatched
• '[': x = 1
• '[': x = 2
• '[': x = 3
• Result: x = 3, minimum swaps = (3 + 1) >> 1 = 2

The algorithm runs in O(n) time with O(1) space complexity.

Example Walkthrough

Let's walk through the string s = "]][[[" to illustrate the solution approach.

Initial Setup:

• String: "]]][["
• Counter x = 0 (tracks unmatched opening brackets)

Step-by-step traversal:

1. Index 0: ']'

   • Check if x > 0? No (x = 0)
   • This ']' remains unmatched
   • x stays at 0

2. Index 1: ']'

   • Check if x > 0? No (x = 0)
   • This ']' remains unmatched
   • x stays at 0

3. Index 2: ']'

   • Check if x > 0? No (x = 0)
   • This ']' remains unmatched
   • x stays at 0

4. Index 3: '['

   • Found an opening bracket
   • Increment x: x = 1

5. Index 4: '['

   • Found an opening bracket
   • Increment x: x = 2

6. Index 5: '['

   • Found an opening bracket
   • Increment x: x = 3

After traversal:

• x = 3 unmatched opening brackets
• This means we also have 3 unmatched closing brackets
• Pattern formed: "]]][[[" (3 closing followed by 3 opening)

Calculate minimum swaps:

• Formula: (x + 1) >> 1 = (3 + 1) >> 1 = 4 >> 1 = 2
• We need 2 swaps

Verification:

• First swap: Swap ']' at index 0 with '[' at index 3 → "[]][]["
• Second swap: Swap ']' at index 2 with '[' at index 4 → "[][[]]"
• Result: "[][[]]" is balanced!

Each swap fixes two pairs because:

• The '[' moved left can now match with a ']' on its right
• The ']' moved right can now match with a '[' on its left

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the algorithm iterates through each character in the string exactly once using a single for loop. Each operation inside the loop (checking the character, incrementing or decrementing x) takes constant time O(1).

The space complexity is O(1). The algorithm only uses a single integer variable x to track the count of unmatched opening brackets, which requires constant extra space regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Tracking Both Opening and Closing Brackets Separately

A common mistake is trying to maintain separate counters for unmatched opening and closing brackets, which complicates the logic unnecessarily.

Incorrect approach:

def minSwaps(self, s: str) -> int:
    unmatched_open = 0
    unmatched_close = 0
  
    for char in s:
        if char == "[":
            if unmatched_close > 0:
                unmatched_close -= 1
            else:
                unmatched_open += 1
        else:  # char == "]"
            if unmatched_open > 0:
                unmatched_open -= 1
            else:
                unmatched_close += 1
  
    return (unmatched_open + 1) // 2  # or (unmatched_close + 1) // 2

Why it's problematic: This approach processes brackets in the wrong order - it tries to match opening brackets with previous closing brackets, which doesn't align with the natural left-to-right matching of balanced strings.

Solution: Use a single counter that only tracks unmatched opening brackets. When encountering a closing bracket, only match it with previous opening brackets, not future ones.

2. Misunderstanding the Final Calculation

Another pitfall is incorrectly calculating the minimum swaps from the unmatched count.

Common mistakes:

• Using unmatched_open // 2 instead of (unmatched_open + 1) // 2
• Forgetting that each swap fixes exactly 2 pairs of brackets

Example demonstrating the issue:

# Wrong calculation
def minSwaps(self, s: str) -> int:
    unmatched_open = 0
    for char in s:
        if char == "[":
            unmatched_open += 1
        elif unmatched_open > 0:
            unmatched_open -= 1
  
    return unmatched_open // 2  # WRONG! Doesn't handle odd numbers correctly

For a string like "]][[" where unmatched_open = 2, the correct answer is (2 + 1) // 2 = 1 swap, not 2 // 2 = 1 (happens to be correct here, but fails for odd counts).

For a string like "]]][[[" where unmatched_open = 3, the correct answer is (3 + 1) // 2 = 2 swaps, not 3 // 2 = 1 swap.

Solution: Always use ceiling division, which can be implemented as (unmatched_open + 1) // 2 or (unmatched_open + 1) >> 1.

3. Attempting to Track Actual Positions for Swapping

Some might try to track the actual indices of brackets that need to be swapped, which significantly increases complexity.

Overcomplicated approach:

def minSwaps(self, s: str) -> int:
    unmatched_close_indices = []
    unmatched_open_indices = []
  
    for i, char in enumerate(s):
        if char == "[":
            unmatched_open_indices.append(i)
        else:
            if unmatched_open_indices:
                unmatched_open_indices.pop()
            else:
                unmatched_close_indices.append(i)
  
    # Now try to pair indices for swapping...
    # This becomes unnecessarily complex

Solution: Recognize that we only need the count of swaps, not the actual swap operations. The mathematical relationship between unmatched brackets and minimum swaps eliminates the need to track positions.