Algorithms & Data Structures : Leetcode 1898. Maximum Number of Removable Characters

題目：

Maximum Number of Removable Characters - LeetCode

很有趣的一個題目，一開始往錯誤的方向想，導致實作太過複雜了（沒有在周賽的一個半小時內寫出來 QQ）。目前周賽還是只能寫出 2~3 題，希望可以練到穩定三題，之後再往四題的目標前進。

這題若是有想到 binary search 的話，程式碼寫起來就會相當簡單了，這類題目我常常沒辦法立刻往 binary search 的方向想，所以紀錄一下。

這題也是看到 related topics 是 binary search 才往 binary search 想的。

我的醜解法：

class Solution {
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        int ans = 0;
        
        int left = 0;
        int right = removable.size() - 1;
        
        while(left <= right) {
            int mid = (left + right) / 2;
            int index = 0;
            unordered_map<int, bool> um_removed;
            for(int i = 0;i <= mid;i++) {
                um_removed[removable[i]] = true;
            }
            for(int i = 0;i < s.size();i++) {
                if(um_removed.find(i) == um_removed.end() && s[i] == p[index]) {
                    index++;
                }
                if(index == p.size()) {
                    break;
                }
            }
            
            if(index == p.size()) {
                left = mid + 1;
                
                ans = max(ans, mid + 1);
            } else {
                right = mid - 1;
            }
        }
        
        return ans;
    }
 };

時間複雜度：每輪遍尋需要 O(N)，因為使用的是 binary search，共需遍尋 O(logN) 次，總共是 O(N*logN)。

高手的解法：

https://leetcode.com/problems/maximum-number-of-removable-characters/discuss/1268446/Binary-Search

我原本每次遍尋 string s 的時候，都需要用 unordered_map 來重新構築 removable 有哪些，而這個高手寫的 code 就簡化了這部份。使用 map 來紀錄 map[ s 被刪掉的 index ] = 此刪除動作是第幾個 removable。這樣在 while 裡面遍尋的時候，就不用樣我那樣每輪都構築 unordered_map。

我原本錯誤的想法：

程式碼很醜，答案也不正確。
一開始先記住 p 的每個字元用的是 s 的哪些 index。並用另外一張表 ( vector<vector<int>> sv = vector<vector<int>>(26); ) 來紀錄每個字元各在 s 的哪些 index 會出現。

再來開始遍尋 removable，每當刪到 p 正在使用的字元，就查 sv 這張表，拿同字元的其他 index。

接下來檢查 p 所使用的所有 s 的 index 是不是仍符合 sequence
( p[n] 所使用的 index 不能比 p[n + 1] 大 )，若不符合，則將每個被推擠到的 p[n] 使用同字元的後一個沒有被刪除的 index，若已經沒有同字元的後一個 index 可以使用，則表示我們沒辦法再繼續進行刪除了，並 return 答案。

class Solution {
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        unordered_map<int, bool> um_removed;
        unordered_map<int, int> um_p;
        
        vector<vector<int>> sv = vector<vector<int>>(26);
        vector<int> pv = vector<int>(p.size(), -1); 
        vector<int> iv = vector<int>(26, 0);
        int ans = 0;
        int index = 0;
        
        for(int i = 0;i < s.size();i++) {
            sv[s[i] - 'a'].push_back(i);
        }
        for(int i = 0;i < p.size();i++) {
            pv[i] = iv[p[i] - 'a'];
            um_p[sv[p[i] - 'a'][iv[p[i] - 'a']]] = i;
            printf("%d\n", sv[p[i] - 'a'][iv[p[i] - 'a']]);
            
            iv[p[i] - 'a']++;
        }
        
        
        for(int i = 0;i < removable.size();i++) {
            if(um_p.find(removable[i]) == um_p.end()) {
                ans++;
                um_removed[removable[i]] = true;
            } else {
                int pindex = um_p[removable[i]];
                
                int flag = 1;
                for(int i = pindex;i < pv.size();i++) {
                    if(i == pindex) {
                        int nowIndex = pv[i];
                        nowIndex++;
                        while(nowIndex < iv[p[i] -'a'] && um_removed.find(sv[p[i] - 'a'][iv[p[i] - 'a']]) != um_removed.end()) {
                            nowIndex++;
                        }
                        if(nowIndex < sv[p[i] - 'a'].size()) {
                            pv[i] = nowIndex;
                        } else {
                            flag = 0;
                        }
                    } else {
                        if(sv[p[i - 1] - 'a'][iv[p[i - 1] - 'a']] > sv[p[i] - 'a'][iv[p[i] - 'a']]) {
                            int nowIndex = pv[i];
                            nowIndex++;
                            while(nowIndex < iv[p[i] -'a'] && um_removed.find(sv[p[i] - 'a'][iv[p[i] - 'a']]) != um_removed.end() && sv[p[i] - 'a'][iv[p[i] - 'a']] < sv[p[i - 1] - 'a'][iv[p[i - 1] - 'a']]) {
                                nowIndex++;
                            }
                            if(nowIndex < sv[p[i] - 'a'].size()) {
                                pv[i] = nowIndex;
                            }
                        }
                    }
                }
                
                
                if(flag == 0)
                    break;
                else 
                    ans++;
            }
        }
        
        
        return ans;
    }
 };