MediumRating 1913
1898. Maximum Number of Removable Characters
arraytwo-pointersstringbinary-search
解題說明
Maximum Number of Removable Characters
題目描述：
給定字串 s、字串 p（p 是 s 的子序列），以及整數陣列 removable（包含 s 中要按順序移除的字元索引）。求最多可以移除 removable 中前 k 個索引對應的字元，使得 p 仍然是修改後的 s 的子序列。回傳最大的 k。
解題思路： 二分搜尋答案 k。
- k 具有單調性：如果移除前 k 個字元後 p 仍是子序列，那移除前 k-1 個也一定是。
- 對 k 進行二分搜尋，範圍 [0, removable.length]。
- 對於每個候選 k，標記
removable[0..k-1]的位置為已移除，然後用雙指標驗證 p 是否仍是 s 的子序列。 - 子序列驗證：用兩個指標分別遍歷 s 和 p，跳過被移除的位置，檢查 p 能否完全匹配。
C++ 解法
複雜度分析
時間複雜度：O((n + r) log r) — 二分搜尋 O(log r) 次，每次驗證 O(n + k)，其中 n = s.length, r = removable.length。
空間複雜度：O(n) — 布林陣列標記被移除的位置。
虛擬碼
1. Binary search on k in range [0, removable.length]
2. For each candidate k (mid):
a. Mark removable[0..k-1] positions as removed
b. Check if p is a subsequence of s (skipping removed positions)
- Two pointers: i on s, j on p
- Skip removed[i]; match s[i] == p[j] → advance j
- Return j == p.length
3. If subsequence check passes: lo = mid (try larger k)
Else: hi = mid - 1
4. Return lo其他解法
線性掃描 O(n × r)：對 k = 0, 1, 2, ...，依次移除字元並檢查子序列。一旦失敗回傳 k-1。每次檢查 O(n)，最壞 O(n × r)。利用了單調性但沒有二分搜尋那麼高效。
增量式維護：記錄每次移除後 p 的匹配位置，只在受影響區域重新匹配。理論上可以更快，但實現非常複雜。
延伸思考
- 如果 removable 中的移除順序不固定（可以任意選 k 個位置移除），問題變成 NP-hard 嗎？
- 如果 p 不是子序列而是子串（連續），二分搜尋仍然適用嗎？
- 如何將此方法推廣到多個模式串（多個 p 都必須保持為子序列）？