題目出處
921. Minimum Add to Make Parentheses Valid
難度
medium
題目分類
String, Stack, Greedy, Bracket Sequences
2026-10-06 一刷
個人範例程式碼 - 一刷 (2026/10/06)
class Solution:
def minAddToMakeValid(self, s: str) -> int:
must_add = 0
remain_left = 0
for c in s:
if c == '(':
remain_left += 1
else:
if remain_left > 0: # match one (
remain_left -= 1
else: # no ( to process )
must_add += 1
return must_add + remain_left
算法說明
簡單的計數題目（stack 壓縮成 counter），體感像偏 easy 的題目。
只需要處理三種條件：
- 出現「)」且左括號計數器 > 0 時，配對成功，計數器 - 1
- 當左括號計數器 == 0，出現 「)」時，must_add + 1 (補左括弧)
- 最後結算時，看還有多少左括弧，因此最後會是 must_add + remain_left 把缺少的左、右括弧全補上
Time Complexity
O(n)
Space Complexity
O(1)