Maximum Number of Removable Characters

How it works

Instead of using a hash set to track removed indices (which adds overhead), we can directly modify the string by replacing removed characters with a placeholder character (like '#'). This avoids hash lookups during the subsequence check.

The binary search logic remains the same, but the subsequence check becomes simpler since we just compare characters, skipping any '#' naturally by checking for equality.

Steps

1. Binary search over the number of removals with l = 0 and r = length of removable.
2. For each midpoint mid:
   • Create a copy of s as a character array.
   • Mark positions removable[0..mid] as '#'.
   • Check if p is a subsequence (characters equal to '#' will never match).
   • If yes, move l = mid + 1.
   • If no, move r = mid.
3. Return l as the maximum number of removals.

Complexity

• Time complexity: O((n + m) * log k)
• Space complexity: O(n)

Where n and m are the lengths of the given strings s and p respectively. k is the size of the array removable.

Things to watch for

Off-by-One Errors in Binary Search Bounds

When setting up binary search, a common mistake is using incorrect bounds or midpoint calculations. The search space is 0 to len(removable), not 0 to len(removable) - 1, because we need to consider removing zero characters as a valid option. Additionally, confusing l < r vs l <= r loop conditions leads to either infinite loops or missing valid answers.

Modifying the Original String Instead of Using a Copy

When marking characters as removed (using '#' or similar), forgetting to create a fresh copy of the string for each binary search iteration causes state to persist incorrectly. The removed characters from a previous iteration pollute subsequent checks, leading to wrong results.

Incorrect Subsequence Check Logic

The subsequence check must skip removed indices while still correctly advancing through both strings. A common bug is incrementing the pattern pointer even when the current character is marked as removed, or failing to increment the source pointer when characters do not match. Both lead to incorrect subsequence determinations.

from typing import List

class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
        l, r = 0, len(removable)
        n, m = len(s), len(p)

        def isSubseq(tmpS):
            i1 = i2 = 0
            while i1 < n and i2 < m:
                if tmpS[i1] == p[i2]:
                    i2 += 1
                i1 += 1
            return i2 == m

        while l < r:
            mid = l + (r - l) // 2
            tmpS = list(s)

            for i in range(mid + 1):
                tmpS[removable[i]] = '#'

            if isSubseq(tmpS):
                l = mid + 1
            else:
                r = mid

        return l

class Solution {
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        int l = 0, r = removable.size();
        int n = s.size(), m = p.size();

        while (l < r) {
            int mid = l + (r - l) / 2;
            string tmpS = s;

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

            if (isSubseq(tmpS, p)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        return l;
    }

private:
    bool isSubseq(const string& s, const string& p) {
        int i1 = 0, i2 = 0, n = s.size(), m = p.size();

        while (i1 < n && i2 < m) {
            if (s[i1] == p[i2]) {
                i2++;
            }
            i1++;
        }
        return i2 == m;
    }
};