08 Valid Parenthesis String — Interview English Script (C++)
Source aligned with: docs/13_Greedy/08_Valid_Parenthesis_String.md
Quick links: Source Solution · Chapter Script Index · Global Index
1) 30-second problem restatement script
| English line | Traditional Chinese meaning (short) | Interview stage |
| Let me restate valid parenthesis string. | 我先重述 Valid Parenthesis String。 | Restatement |
| String contains left parenthesis, right parenthesis, and star. | 字串包含 (、)、*。 | Restatement |
| Star can act as left parenthesis, right parenthesis, or empty. | * 可當左括號、右括號或空字元。 | Restatement |
| We need to decide if whole string can be valid. | 要判斷整串是否可能合法。 | Restatement |
| Valid means proper matching order of parentheses. | 合法代表括號配對順序正確。 | Restatement |
| I will use greedy range of possible open counts. | 我會用開括號可能數量區間的貪心法。 | Restatement |
2) Clarifying questions (5 lines)
| English line | Traditional Chinese meaning (short) | Interview stage |
| Do we require full-string validity, not partial? | 是否要求整字串完全合法，不是局部？ | Clarify |
| Can star be interpreted independently at each position? | 每個 * 是否可獨立選解釋？ | Clarify |
| Is string length up to one hundred in constraints? | 限制是否長度最多 100？ | Clarify |
| Should result be boolean only? | 結果是否只要布林值？ | Clarify |
| Is O(n) greedy expected instead of DP/backtracking? | 是否期望 O(n) 貪心而非 DP/回溯？ | Clarify |
3) Approach discussion
Brute force (3 lines)
| English line | Traditional Chinese meaning (short) | Interview stage |
| Brute force branches three ways for each star. | 暴力法對每個 * 都分三支。 | Approach |
| That yields exponential search tree quickly. | 搜尋樹會快速指數膨脹。 | Approach |
| We need a compact greedy invariant. | 我們需要緊湊的貪心不變量。 | Approach |
Optimized approach (5 lines)
| English line | Traditional Chinese meaning (short) | Interview stage |
| Track minimum and maximum possible open parenthesis counts: leftMin and leftMax. | 追蹤開括號可能最小值 leftMin 與最大值 leftMax。 | Approach |
| For left parenthesis, both bounds increase by one. | 遇到 ( 時兩個界都加一。 | Approach |
| For right parenthesis, both bounds decrease by one. | 遇到 ) 時兩個界都減一。 | Approach |
| For star, leftMin decreases and leftMax increases. | 遇到 * 時 leftMin 減一、leftMax 加一。 | Approach |
| If leftMax ever drops below zero return false; clamp leftMin at zero, and finally require leftMin equals zero. | 若 leftMax<0 立即 false；leftMin 小於 0 要夾回 0；最後需 leftMin==0。 | Approach |
4) Coding-and-speaking script (line-by-line, in coding order)
| English line | Traditional Chinese meaning (short) | Interview stage |
| I initialize leftMin and leftMax as zero. | 我初始化 leftMin=0、leftMax=0。 | Coding |
| For each character c in s, I update bounds by type. | 對每個字元 c 依類型更新區間界。 | Coding |
| If c is left parenthesis, increment both bounds. | 若 c 是 (，兩界都加一。 | Coding |
| If c is right parenthesis, decrement both bounds. | 若 c 是 )，兩界都減一。 | Coding |
| If c is star, decrement leftMin and increment leftMax. | 若 c 是 *，leftMin--、leftMax++。 | Coding |
| If leftMax becomes negative, return false immediately. | 若 leftMax 變負，立即回 false。 | Coding |
| If leftMin becomes negative, reset it to zero. | 若 leftMin 變負，重設為 0。 | Coding |
| After loop, return whether leftMin equals zero. | 迴圈後回傳 leftMin 是否為 0。 | Coding |
| English line | Traditional Chinese meaning (short) | Interview stage |
| Let me dry-run s equal star right-right sequence "(*))". | 我手跑 s="(*))"。 | Dry-run |
| After left parenthesis, both bounds become one. | 遇 ( 後兩界都變 1。 | Dry-run |
| Star makes leftMin zero and leftMax two. | * 後 leftMin=0、leftMax=2。 | Dry-run |
| Next right parenthesis gives leftMin minus one and leftMax one, then clamp leftMin to zero. | 下一個 ) 使 leftMin=-1、leftMax=1，再把 leftMin 夾到 0。 | Dry-run |
| Final right parenthesis gives leftMin minus one and leftMax zero, clamp leftMin to zero again. | 最後 ) 使 leftMin=-1、leftMax=0，再次把 leftMin 夾到 0。 | Dry-run |
| leftMax never went negative during scan. | 掃描中 leftMax 從未小於 0。 | Dry-run |
| Final leftMin is zero, so string is valid. | 最終 leftMin=0，因此字串合法。 | Dry-run |
6) Edge/corner test script (at least 4 cases)
| English line | Traditional Chinese meaning (short) | Interview stage |
| Case one: simple balanced parentheses without stars. | 案例一：無星號的普通平衡括號。 | Edge test |
| Case two: all stars only string. | 案例二：全是 * 的字串。 | Edge test |
| Case three: prefix with too many right parentheses should fail early. | 案例三：前綴右括號過多要提早失敗。 | Edge test |
| Case four: stars must be used as empty to succeed. | 案例四：需要把 * 當空字元才成功。 | Edge test |
| Case five: stars must be used as left parentheses to succeed. | 案例五：需要把 * 當左括號才成功。 | Edge test |
7) Complexity script
Short version (2 lines)
| English line | Traditional Chinese meaning (short) | Interview stage |
| Time complexity is O(n). | 時間複雜度是 O(n)。 | Complexity |
| Space complexity is O(1). | 空間複雜度是 O(1)。 | Complexity |
Full version (4 lines)
| English line | Traditional Chinese meaning (short) | Interview stage |
| We process each character exactly once. | 每個字元只處理一次。 | Complexity |
| Each step does constant-time bound updates. | 每步僅做常數時間界值更新。 | Complexity |
| Hence runtime is linear O(n). | 因此時間是線性 O(n)。 | Complexity |
| Only two integer bounds are stored, so memory is O(1). | 只存兩個整數界值，空間 O(1)。 | Complexity |
8) If stuck rescue lines (10 lines)
| English line | Traditional Chinese meaning (short) | Interview stage |
| Let me think in range of possible open counts. | 我改用可能開括號數量區間思考。 | If stuck |
| leftMin is minimum possible opens. | leftMin 是最小可能開括號數。 | If stuck |
| leftMax is maximum possible opens. | leftMax 是最大可能開括號數。 | If stuck |
| Star expands flexibility by lowering min and raising max. | * 會降低最小值並提高最大值。 | If stuck |
| leftMax below zero means impossible immediately. | leftMax 小於 0 代表立即不可能。 | If stuck |
| leftMin below zero should be clamped to zero. | leftMin 小於 0 要夾回 0。 | If stuck |
| Clamp means we choose some stars as empty or left. | 夾回 0 代表把某些 * 改當空或左。 | If stuck |
| Let me test quickly with ")(" for early failure. | 我快速測 )( 的提早失敗。 | If stuck |
| leftMax drops negative at first char, so false. | 第一個字就讓 leftMax 變負，因此 false。 | If stuck |
| Great, invariant now feels clear. | 很好，不變量現在很清楚。 | If stuck |
9) Final wrap-up lines (5 lines)
| English line | Traditional Chinese meaning (short) | Interview stage |
| I solved this with greedy open-count range tracking. | 我用開括號區間追蹤的貪心法解了這題。 | Wrap-up |
| leftMin and leftMax capture all star interpretations compactly. | leftMin 與 leftMax 可緊湊涵蓋所有 * 解釋。 | Wrap-up |
| Early failure is detected by leftMax below zero. | leftMax<0 可提早判定失敗。 | Wrap-up |
| Final validity requires leftMin equals zero. | 最終合法需 leftMin==0。 | Wrap-up |
| Complexity is O(n) time and O(1) space. | 複雜度是 O(n) 時間、O(1) 空間。 | Wrap-up |
10) Ultra-short cheat sheet (20 lines total)
| English line | Traditional Chinese meaning (short) | Interview stage |
| Goal: check if string with star can be valid parentheses. | 目標：判斷含 * 字串能否成合法括號。 | Cheat sheet |
| Star can be left right or empty. | * 可當左、右或空。 | Cheat sheet |
| Track leftMin and leftMax. | 追蹤 leftMin 與 leftMax。 | Cheat sheet |
| '(' -> leftMin++, leftMax++. | ( -> leftMin++、leftMax++。 | Cheat sheet |
| ')' -> leftMin--, leftMax--. | ) -> leftMin--、leftMax--。 | Cheat sheet |
| '*' -> leftMin--, leftMax++. | * -> leftMin--、leftMax++。 | Cheat sheet |
| If leftMax<0 -> false. | 若 leftMax<0 -> false。 | Cheat sheet |
| If leftMin<0, clamp to 0. | 若 leftMin<0，夾到 0。 | Cheat sheet |
| After scan, require leftMin==0. | 掃描後需 leftMin==0。 | Cheat sheet |
| This guarantees some interpretation is valid. | 這保證至少有一種解釋合法。 | Cheat sheet |
| Example "(*)" -> true. | 範例 "(*)" -> true。 | Cheat sheet |
| Example "(*))" -> true. | 範例 "(*))" -> true。 | Cheat sheet |
| Example ")(" -> false. | 範例 ")(" -> false。 | Cheat sheet |
| Time O(n). | 時間 O(n)。 | Cheat sheet |
| Space O(1). | 空間 O(1)。 | Cheat sheet |
| Common bug: forget clamping leftMin. | 常見錯誤：忘記夾回 leftMin。 | Cheat sheet |
| Common bug: only track one count. | 常見錯誤：只追蹤單一計數。 | Cheat sheet |
| Range idea is key insight. | 區間思路是核心洞察。 | Cheat sheet |
| Early-fail condition saves work. | 提早失敗條件可節省工作。 | Cheat sheet |
| Explain star flexibility explicitly. | 需明確說明 * 的彈性角色。 | Cheat sheet |
Quality check
- Consistency with source solution: ✅ leftMin/leftMax greedy invariant preserved.
- No hallucinated constraints: ✅ Dot/star-free parenthesis semantics maintained.
- Language simplicity: ✅ Clear interview-safe explanation of range updates.