Description
給定字串
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#
k 越大越不可能滿足，具有單調性。在 [0, removable.size] 上二分搜尋最大的 k。
- 移除越多字元，p 越不容易是 s 的子序列 – 單調性
- 對於給定的 k，標記前 k 個 removable 索引為「已刪除」，然後檢查 p 是否仍是 s 的子序列
Approaches#
1: Binary Search on Answer#
- 概念: 在 [0, removable.size] 上二分搜尋最大的 k，用子序列檢查驗證
- 時間複雜度:
O((n + m) * log(removable.size))，n = |s|, m = removable.size - 空間複雜度:
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
}
}這是找最大可行值，使用
left = mid配合向上取整的mid。子序列判斷使用雙指標，跳過已標記刪除的字元。
🔑 Takeaways#
- Pattern: Binary Search on Answer（找最大可行值）
- 關鍵技巧: 識別單調性是關鍵 – 移除越多字元越不可能滿足條件。驗證函式用 boolean 陣列標記刪除位置，再做子序列判斷