Description

Submission

class Solution {
    // returns true if t is a substring of s
    bool isSub(const string& s, const string& t) {
        for(int i = 0, j = 0; i < s.length(); ++i) {
            if(s[i] == t[j]) {
                if(++j == t.length()) return true;
            }
        }
        return false;
    }
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        int left = 0, right = min(s.length() - p.length(), removable.size());

        while(left < right) {
            int mid = right - (right - left) / 2;

            string t = s;

            for(int i = 0; i < mid; ++i) {
                t[removable[i]] = '#';
            }

            if(isSub(t, p)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
};