⚡Flashcard Drill➔
NeetCode #369LC-921MediumStack
← Back to All Problems

#369 · #921 · Minimum Add to Make Parentheses Valid(使括号有效的最少添加)

📌 Problem Statement & Constraints

A parentheses string is valid if it is empty, or can be written as AB or (A) where A and B are valid. Given a string s, return the minimum number of parentheses to insert to make it valid. Constraints: 1 <= s.length <= 1000.

💡 Core Algorithmic Approaches

  1. Scan left to right with a counter of unmatched opening brackets.
  2. On (, increment. On ), decrement if possible; if there is nothing to match, that ) must be fixed by an insertion, so increment the answer.
  3. At the end, any unmatched ( also needs one insertion each.
  4. The answer is insertions_for_closing + unmatched_opening.

💻 Benchmark Python3 Implementation

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        opening = 0                        # unmatched '(' so far
        need = 0                           # insertions needed for stray ')'
        for ch in s:
            if ch == "(":
                opening += 1
            elif opening > 0:
                opening -= 1               # matched
            else:
                need += 1                  # unmatched ')' -> insert a '('
        return need + opening              # plus one insertion per leftover '('

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): two counters, no stack needed since only the counts matter.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the leftover opening brackets: they each need one closing insertion.
  • Using a stack: it works but uses O(n) space for information that two counters capture.
  • Decrementing opening below zero: that would conflate stray ) with matched pairs; the else branch is required.
  • Assuming the answer is abs(balance): that ignores the order, so ")(" would give 0 instead of the correct 2.
⚡
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 Stack Problems