Min Swaps Balanced String LeetCode 1963

LeetCode 1963 Minimum Number of Swaps to Make the String Balanced gives you a string of only "[" and "]" characters with an equal number of each. You are allowed to swap any two characters in the string any number of times. The goal is to return the minimum number of swaps required to make the string balanced.

A balanced string is one where every prefix has at least as many open brackets as close brackets — equivalently, no "]" ever appears before its matching "[". Because the total counts of "[" and "]" are equal, a balanced string here means the string can be fully matched into valid bracket pairs.

The naive approach of trying all possible swaps is exponential. The key insight is that you do not need to simulate swaps at all — a single greedy scan lets you count unmatched brackets, and the answer follows directly from that count via a simple formula.

Scan the string from left to right while maintaining a counter for unmatched open brackets. When you encounter "[", increment the open counter — this bracket is potentially matchable. When you encounter "]", check if the open counter is greater than zero: if so, decrement it to cancel a matched pair. If open is zero, this "]" has no matching "[" before it and is unmatched.

After the full scan, the unmatched close brackets (the ones we counted) are all to the left of the unmatched open brackets. This is because we cancelled every "[" that could be matched by a preceding or subsequent "]" in natural order. What remains forms a suffix of the form "]]]..[[[" — all unmatched closes then all unmatched opens.

The number of unmatched closes equals the number of unmatched opens (since the total counts are equal). Call this count "unmatched" (= the close count from our scan, which equals the final open count). The problem reduces to: how many swaps does it take to fix a sequence of k unmatched closes followed by k unmatched opens?

The counting algorithm uses just two integer variables: open and close, both starting at zero. Iterate through every character in the string. When the character is "[", increment open. When the character is "]" and open is greater than zero, decrement open (a match was made). When the character is "]" and open is zero, increment close (this close bracket is unmatched).

At the end of the scan, open and close will be equal (because the input guarantees equal total counts of "[" and "]"). The variable close holds the number of unmatched close brackets, which is also the number of unmatched open brackets. This is the value we use in the formula.

The entire counting step runs in O(n) time and O(1) space — no stack, no auxiliary array, no sorting. Just two counters updated in a single left-to-right pass over the string.

After cancellation, the unmatched portion looks like: "]]]..[[[" with k unmatched closes followed by k unmatched opens. The leftmost "]" and rightmost "[" are the perfect candidates for a swap — swapping them produces "[[...]]" which fixes one "]" that was too early and one "[" that was too late, simultaneously resolving two unmatched brackets at once.

Each such swap reduces the unmatched count by exactly 2 — it converts one unmatched "]" into "[" (now a valid open before many closes) and one unmatched "[" into "]" (now a valid close after many opens). This means k pairs of unmatched brackets can be fixed with k/2 swaps if k is even, or (k+1)/2 swaps if k is odd (the last swap fixes only one remaining unmatched pair when k is odd, though it still only takes one swap).

The formula (unmatched + 1) // 2 in integer arithmetic gives ceil(unmatched / 2). This is the minimum — no strategy can do better because each swap can resolve at most 2 unmatched brackets, so you need at least ceil(k/2) swaps to eliminate k unmatched brackets.

Consider s = "][][". Trace the cancellation pass: index 0 is "]", open=0 so close=1; index 1 is "[", open=1; index 2 is "]", open>0 so open=0 (cancel); index 3 is "[", open=1. End state: open=1, close=1. Unmatched = 1 (one unmatched close and one unmatched open remain).

The answer is ceil(1 / 2) = 1 swap. Verify: swap index 0 ("]") with index 3 ("["): we get "[][][" — wait, s has length 4. Swapping positions 0 and 3 turns "][][" into "[]][" — that is still not balanced. Let us swap positions 0 and 1 instead: "[][]" — balanced in 1 swap. Answer confirmed = 1.

Now consider s = "]][[". Trace: index 0 "]" → close=1; index 1 "]" → close=2; index 2 "[" → open=1; index 3 "[" → open=2. End state: open=2, close=2. Unmatched=2. Answer = ceil(2/2) = 1 swap. Swap index 0 and index 3: "[[]]" — balanced in 1 swap. Confirmed.

Python solution: def minSwaps(s: str) -> int: open = 0; close = 0; for c in s: if c == "[": open += 1; elif open > 0: open -= 1; else: close += 1; return (close + 1) // 2. The loop runs in O(n) and the two variables give O(1) space. The return expression uses integer division to compute ceil(close / 2).

Java solution: public int minSwaps(String s) { int open = 0, close = 0; for (char c : s.toCharArray()) { if (c == "[") open++; else if (open > 0) open--; else close++; } return (close + 1) / 2; } This is identical logic in Java. The (close + 1) / 2 expression performs integer floor division which equals ceil(close / 2) for non-negative integers.

Both solutions are O(n) time and O(1) space. The only difference from a naive stack-based solution is that we use a counter instead of an actual stack — since we only ever need to know whether the stack is empty (open > 0) and what its size is (the open counter), no actual stack data structure is necessary.

Valid Parentheses (LeetCode 20) is the canonical bracket-matching problem — it checks whether a string of mixed bracket types is fully balanced using a stack. Solving it first builds the intuition for why unmatched brackets accumulate and how close/open counting relates to stack depth. LeetCode 1963 extends that intuition from validation to repair.

Generate Parentheses (LeetCode 22) asks you to generate all valid combinations of n pairs of parentheses, using backtracking with the invariant that at each step open <= n and close <= open. The same open/close balance constraint that drives generation in LeetCode 22 is what you repair in LeetCode 1963.

Minimum Add to Make Parentheses Valid (LeetCode 921) and Remove Invalid Parentheses (LeetCode 301) are close relatives — they also count unmatched brackets using the same open/close counter pattern and then compute a minimum-edit answer. The bracket balancing family all shares the core counting technique; swaps (1963), additions (921), and removals (301) are different repair strategies on the same unmatched-count foundation.