NeetCode #116LC-1963MediumArrays & Hashing
← Back to All Problems#116 · #1963 · Minimum Number of Swaps to Make the String Balanced(使字符串平衡的最少交换次数)
📌 Problem Statement & Constraints
Given a 0-indexed string
s of even length consisting of [ and ], return the minimum number of swaps (of any two indices) needed to make it balanced. Constraints: 1 <= s.length <= 10^5.💡 Core Algorithmic Approaches
- Scan the string tracking the running balance:
[adds 1,]subtracts 1. - Record the deepest negative dip -- that is, the largest deficit of opening brackets encountered so far.
- Each swap can fix exactly two unmatched brackets (one misplaced
]and one misplaced[), so the answer isceil(max_deficit / 2). - Equivalently, count the maximum nesting depth of unmatched closing brackets and halve it, rounding up.
💻 Benchmark Python3 Implementation
class Solution:
def minSwaps(self, s: str) -> int:
depth = 0
max_deficit = 0
for ch in s:
if ch == "[":
depth += 1
else:
depth -= 1
max_deficit = max(max_deficit, -depth) # deepest unmatched ']' deficit
return (max_deficit + 1) // 2 # each swap fixes two brackets⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): two counters.
⚠️ Interview Pitfalls & Follow-ups
- Using a stack and counting unmatched brackets, then dividing by 2 with truncation: the count of unmatched
]is exactly the max deficit, and the halving must round up. - Returning
max_deficit: each swap fixes one]and one[, so the answer is half. - Simulating actual swaps: unnecessary and error-prone; the deficit bound is exact.
- Ignoring the guaranteed even length: it ensures the string can always be balanced.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.