Medium

Minimum Number of Swaps to Make the String Balanced

LAB

Given a bracket string with equal [ and ], return the minimum swaps needed to make it balanced.

EXAMPLES

Example 1

Input
{
  "s": "][]["
}

Output
1

FUNCTION SHAPE

s: string→int

SOLUTION NOTE

After removing matched pairs, we have "]]][[[" pattern. Each swap fixes 2 brackets, so ceil(unmatched/2).

Reveal reference solution +

pythonREFERENCE

def minSwaps(self, s: str) -> int:
    unmatched = 0
    for c in s:
        if c == '[':
            unmatched += 1
        elif unmatched > 0:
            unmatched -= 1
    return (unmatched + 1) // 2

TimeO(n)

SpaceO(1)

Open on LeetCode ↗