⚡Flashcard Drill➔
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

  1. Scan the string tracking the running balance: [ adds 1, ] subtracts 1.
  2. Record the deepest negative dip -- that is, the largest deficit of opening brackets encountered so far.
  3. Each swap can fix exactly two unmatched brackets (one misplaced ] and one misplaced [), so the answer is ceil(max_deficit / 2).
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems