1898. Maximum Number of Removable Characters - Medium

前往題目

想法

• Binary Search
• 找最大k，所以搜尋k

思路

1. 每次選定k
2. 檢查移除前k個是否結果依然成立，也就是segment是否還存在於原本的字串

需要n次(s的總字數)來判斷是否segment存在，還需要log k次(因為Binary Search)去試要去除幾個，所以複雜度是$n \cdot \log k$

Code

class Solution {
    public int maximumRemovals(String s, String p, int[] removable) {
        int l = 0, r = removable.length;
        int res = 0;
        
        // Search for the maximum k
        while (l <= r) {
            int mid = l + (r - l) / 2;

            // The k is valid
            if (isValid(s, p, removable, mid)) {
                res = mid; // Store k
                l = mid + 1; // Further check if k could be bigger
            } else {
                r = mid - 1; // Search for smaller k
            }
        }
        return res;
    }

    private boolean isValid(String origin, String seg, int[] indexToRemove, int k) {
        // Pointers of origin and seg.
        int i1 = 0, i2 = 0;
        // Add indexToRemove to set for quick decision
        Set<Integer> set = new HashSet();
        for (int i = 0; i < k; ++i) {
            set.add(indexToRemove[i]);
        }
        
        // Check if segment exists
        int matched = 0;
        while (i1 < origin.length() && i2 < seg.length()) {
            if (set.contains(i1)) {
                ++i1;
                continue;
            }

            if (origin.charAt(i1) == seg.charAt(i2)) {
                ++matched;
                ++i2;
            }
            ++i1;
        }

        return matched >= seg.length();
    }
}