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
- Scan left to right with a counter of unmatched opening brackets.
- On
(, increment. On), decrement if possible; if there is nothing to match, that)must be fixed by an insertion, so increment the answer. - At the end, any unmatched
(also needs one insertion each. - 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
openingbelow zero: that would conflate stray)with matched pairs; theelsebranch 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.