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 都必須保持為子序列)?