3316. Find Maximum Removals From Source String

You are given a string source of size n, a string pattern that is a subsequence of source, and a sorted integer array targetIndices that contains distinct numbers in the range [0, n - 1].

We define an operation as removing a character at an index idx from source such that:

• idx is an element of targetIndices.

• pattern remains a subsequence of source after removing the character.

Performing an operation does not change the indices of the other characters in source. For example, if you remove 'c' from "acb", the character at index 2 would still be 'b'.

Return the maximum number of operations that can be performed.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

class Solution {
public:
    int maxRemovals(string source, string pattern, vector<int>& order) {
        int n = source.size(), m = pattern.size();
        vector<int> dp(m + 1, INT_MIN);
        dp[0] = 0;
        for(int i = 0, k = 0; i < n; i++) {
            bool fl = k < order.size() and order[k] == i;
            for(int j = m; j >= 0; j--) {
                if(j + 1 <= m and pattern[j] == source[i]) {
                    dp[j+1] = max(dp[j+1], dp[j]);
                }
                dp[j] += fl;
            }
            if(fl) k++;
        }
        return dp[m];
    }
};