1898. Maximum Number of Removable Characters

1898. Maximum Number of Removable Characters

題意

給定兩個字串 s 跟 p， p 為 s 的 subsequence

給定一個數字陣列 removable，代表從 s 移除字元的 index

• 找出數字 k，代表照著 removable的前 k 個 index 從 s 移除後，s 仍是 p 的 subsequence

• 移除的操作不影響字串長度，即 abc 移除 index 1 之後可視為 a#c 來繼續做移除而不需要改變 removable內的 index 對應到 s 的位置

限制

• 1 <= p.length <= s.length <= 10^5

• 0 <= removable.length < s.length

• 0 <= removable[i] < s.length

• p is a subsequence of s.

• s and p both consist of lowercase English letters.

• The elements in removable are distinct.

思考

• 只取前 k 個做移除，代表在 removable 中找出符合題意的中斷點

  • 例如: s = “abc”, p = “c“, removable = [0,1,2] ⇒ [0, 1] | [2]

• 這種找出陣列中特定位置可用 binary search

  • 若斷點符合條件，往右尋找能不能讓 k 更長

  • 若不符合，則往左尋找答案

Coding 流程

• 先建立一個function，比對移除 k 個元素之後的 s 是否仍讓 p 為 subsequence

• 實做binary search，條件(Left < Right)

  • 上述function為 true 時 Left 移動到 Mid + 1

  • false 則 Right 移動到 Mid

• 最後 left 即為答案

class Solution {
    bool check(string s, string& p, vector<int>& removable, int k) {
        for (int i = 0; i < k; i += 1) {
            s[removable[i]] = '*';
        }

        int i = 0;
        int j = 0;
        while (i < s.size() && j < p.size()) {
            if (s[i] == p[j]) {
                i += 1;
                j += 1;
            } else {
                i += 1;
            }
        }
        return j == p.size();
    }
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        int i = 0;
        int j = removable.size();

        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (check(s, p, removable, mid)) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return j;
    }
};