給定字串
s、字串p和陣列removable（含 s 的索引）。依序移除removable中前 k 個索引對應的字元後，p仍必須是s的子序列。求最大的k。
Example:
Input: s = “abcacb”, p = “ab”, removable = [3,1,0] Output: 2（移除索引 3, 1 後 s 變成 “a_c_cb”，p=“ab” 仍是子序列）
Intuition
TIP
k 越大越不可能滿足，具有單調性。在 [0, removable.size] 上二分搜尋最大的 k。
- 移除越多字元，p 越不容易是 s 的子序列 — 單調性
- 對於給定的 k，標記前 k 個 removable 索引為「已刪除」，然後檢查 p 是否仍是 s 的子序列
Approaches
1. Brute Force: Try Each k Descending — O(m·(n+m)) / O(n)
- Idea: 從刪最多開始往下試，第一個讓 p 仍是子序列的 k 即答案
- Time:
O(m·(n+m))- 最差試遍每個 k，各做一次子序列檢查 - Space:
O(n)- 標記陣列
class Solution {
fun maximumRemovals(s: String, p: String, removable: IntArray): Int {
for (k in removable.size downTo 0) {
if (isSubsequence(s, p, removable, k)) return k
}
return 0
}
private fun isSubsequence(s: String, p: String, removable: IntArray, k: Int): Boolean {
val removed = BooleanArray(s.length)
for (i in 0 until k) removed[removable[i]] = true
var j = 0
for (i in s.indices) {
if (!removed[i] && j < p.length && s[i] == p[j]) j++
}
return j == p.length
}
}⭐ 2. Binary Search on Answer — O((n + m) * log(removable.size)) / O(n)
- Idea: 在 [0, removable.size] 上二分搜尋最大的 k，用子序列檢查驗證
- Time:
O((n + m) * log(removable.size))，n = |s|, m = removable.size - Space:
O(n)（標記陣列）
class Solution {
fun maximumRemovals(s: String, p: String, removable: IntArray): Int {
var left = 0
var right = removable.size
while (left < right) {
val mid = left + (right - left + 1) / 2
if (isSubsequence(s, p, removable, mid)) {
left = mid
} else {
right = mid - 1
}
}
return left
}
private fun isSubsequence(s: String, p: String, removable: IntArray, k: Int): Boolean {
val removed = BooleanArray(s.length)
for (i in 0 until k) {
removed[removable[i]] = true
}
var j = 0
for (i in s.indices) {
if (!removed[i] && j < p.length && s[i] == p[j]) {
j++
}
}
return j == p.length
}
}WARNING
這是找最大可行值，使用 left = mid 配合向上取整的 mid。子序列判斷使用雙指標，跳過已標記刪除的字元。
🔑 Takeaways
- Pattern: Binary Search on Answer（找最大可行值）
- Key trick: 識別單調性是關鍵 — 移除越多字元越不可能滿足條件。驗證函式用 boolean 陣列標記刪除位置，再做子序列判斷