題目描述:
給定字串 s、字串 p(p 是 s 的子序列),以及整數陣列 removable(包含 s 中要按順序移除的字元索引)。求最多可以移除 removable 中前 k 個索引對應的字元,使得 p 仍然是修改後的 s 的子序列。回傳最大的 k。
解題思路: 二分搜尋答案 k。
removable[0..k-1] 的位置為已移除,然後用雙指標驗證 p 是否仍是 s 的子序列。時間複雜度: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 的匹配位置,只在受影響區域重新匹配。理論上可以更快,但實現非常複雜。