3 min read leetcode

1898. Maximum Number of Removable Characters

1898. Maximum Number of Removable Characters
Photo by Markus Spiske / Unsplash

題目連結: 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 對應。

限制

  • 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 都是小寫英文字母。
  • removable 內的元素皆互不重複。

思考

  • 只取前 k 個做移除，代表要在 removable 中找到一個中斷點，使移除後 p 仍能成為 s 的 subsequence。
    • 例如: s = "abc", p = "c", removable = [0, 1, 2] ⇒ 可以想成 [0, 1] | [2] 這樣的切割，確定在哪裡中斷。
  • 這種要在陣列裡找符合條件的中斷點，常可用二元搜尋 (binary search)：
    • 若某個中點 mid 能成功讓 p 成為移除後的 s 的 subsequence，就代表可以嘗試往右再找更大的 k。
    • 若失敗，就往左找更小的 k。

Coding 流程

  1. 先建立一個 check 函式，比對當移除 k 個元素之後，s 是否仍然能讓 p 成為其 subsequence。
  2. 透過二元搜尋 (binary search) 判斷要拿多少個元素來移除：
    • 設定 left = 0、right = removable.size()。
    • 在迴圈裡面計算 mid，呼叫 check(s, p, removable, mid)：
      • 若回傳 true，表示可以再嘗試移除更多，所以令 left = mid + 1。
      • 否則 right = mid - 1。
  3. 最後傳回的答案就是能移除的最大 k (即 right)。

Code

class Solution {
    bool check(string s, string& p, vector<int>& removable, int k) {
        // 先把前 k 個位置的字元標記成 '*' (視為被移除)
        for (int i = 0; i < k; i++) {
            s[removable[i]] = '*';
        }

        // 檢查 p 是否仍為 s 的 subsequence
        int i = 0;
        int j = 0;
        while (i < s.size() && j < p.size()) {
            if (s[i] == p[j]) {
                i++;
                j++;
            } else {
                i++;
            }
        }
        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;
    }
};

複雜度

  • 時間複雜度
    在二元搜尋過程中，最壞情況下需要執行 log⁡(removable.size()) 次，而每次 check 需要線性掃過 s（長度 n）以及比對 p（長度 m）才能判斷是否仍然是 subsequence，所以一次檢查約為 O(n+m)。因此總體時間複雜度約為O((n+m)×log⁡(removable.size()))由於 removable.size() 最多接近 n，可視作O((n+m)log⁡n).
  • 空間複雜度
    函式 check 裡雖然以值傳遞 string s（產生一個 s 的副本），但除此之外並沒有額外使用顯著的資料結構，故額外空間為 O(n)（來自字串複本）。若忽略參數傳遞的影響，也可視為額外空間 O(1)。

Justin