解題說明
Minimum Remove to Make Valid Parentheses
題目描述：給定一個由小寫英文字母和括號 ( 、) 所組成的字串 s，請移除最少數量的括號，使得剩餘的字串是「合法的括號字串」，並回傳任意一個合法結果。合法括號字串的定義是：每個左括號都有對應的右括號，且括號之間正確地嵌套。
解題思路：
本題是 Meta（Facebook）面試中出現頻率最高的題目之一，考察對括號匹配問題的處理能力。
核心思路是使用一個 stack 來追蹤所有「未被匹配的左括號索引」，同時收集「多餘的右括號索引」，最終將所有需要刪除的位置標記起來，重建字串。
詳細步驟：
- 建立一個 stack，用來存放尚未匹配的
(的索引。 - 建立一個 set，用來記錄所有應該被刪除的索引。
- 從左到右遍歷字串：
- 遇到
(：將其索引推入 stack。 - 遇到
)：若 stack 不為空，pop 一個(完成匹配；若 stack 為空，表示這個)沒有對應的(，將其索引加入刪除集合。
- 遇到
- 遍歷結束後，stack 中剩餘的索引都是未匹配的
(，全部加入刪除集合。 - 重建字串，跳過所有在刪除集合中的索引。
此方法只需一次遍歷即可找到所有需要刪除的位置，邏輯清晰，是面試中最推薦的解法。
C++ 解法
複雜度分析
時間複雜度：O(n) — 對字串進行一次線性掃描，每個字元最多被 push 和 pop 各一次；最後重建字串也是 O(n)。整體時間複雜度為 O(n)，其中 n 為字串長度。
空間複雜度：O(n) — stack 最壞情況下存放所有 ( 的索引（例如字串為 ((((），刪除集合最壞情況下也存放 O(n) 個索引。輸出字串另需 O(n) 空間。整體額外空間為 O(n)。
虛擬碼
1. Initialize an empty stack `openStack` and an empty set `toRemove`.
2. For each index i and character c in s:
a. If c == '(': push i onto openStack.
b. If c == ')':
- If openStack is not empty: pop from openStack (matched pair).
- Else: add i to toRemove (unmatched ')').
3. After the loop, pop all remaining indices from openStack into toRemove (unmatched '(').
4. Build result string by appending s[i] for every i not in toRemove.
5. Return result.其他解法
方法一：雙向掃描（Two-Pass）
不使用 stack，改用兩次線性掃描：
- 第一次（左到右）：用計數器
open追蹤未匹配的(。遇到(時open++；遇到)時，若open > 0則open--（匹配成功），否則跳過此)（多餘的右括號）。第一次掃描後，所有多餘的)已被移除。 - 第二次（右到左）：用計數器
close追蹤未匹配的)。對第一次的結果反向掃描，移除多餘的(。
優點是不需要額外的 set 或 stack，空間使用更節省（只有兩個計數器）；缺點是需要構建中間字串，實作上較繁瑣。
方法二：計數器法（Counter-Based，單次掃描）
使用兩個計數器 openCount（未匹配的 ( 數量）和 removeCount（已決定刪除的括號數）。從左到右掃描，動態決定是否保留當前字元：
- 遇到
(：openCount++，加入結果。 - 遇到
)：若openCount > 0則openCount--，加入結果（匹配成功）；否則跳過（多餘的)）。 - 掃描結束後，
openCount即為多餘的(數量，需從結果的尾端往前移除對應數量的(。
此方法空間複雜度最優（無需額外 set），但移除尾端多餘 ( 時需要額外處理，實作稍複雜。
延伸思考
-
若字串中除了
(和)之外，還包含[、]、{、}等多種括號，應如何調整解法以同時處理所有括號的最少移除問題？（提示：stack 中需同時記錄括號類型與索引。） -
本題要求回傳「任意一個」合法結果。若題目改為要求回傳「字典序最小」的合法結果，解法應如何修改？
-
若輸入字串非常長（例如 10^7 個字元），且需要在嚴格的記憶體限制下運行，你會如何優化空間複雜度，避免同時存放原字串、stack、刪除集合和結果字串？