774. How Many Letters May Go

You are given a string s, a shorter string p which is a subsequence of s, and a list of q DISTINCT positions in s called the removal order. Positions are numbered from 0.

For a number t, "applying t removals" means deleting the characters of s at the first t positions of the removal order, all at once. The remaining characters keep their relative order.

Print the largest t for which p is still a subsequence of what remains.

s = abcacb, p = ab, order = 3 1 0 answer 2 after dropping 3 and 1: a c c b s = abcbddddd, p = abcd, order = 3 2 1 4 answer 1 s = abcab, p = abc, order = 0 answer 0 dropping index 0 already breaks it s = abc, p = abc, order = 2 1 0 answer 0 nothing may go

## Why trying removals one at a time is too slow

Applying one more removal and re-testing costs O(|s|) per step, so checking every t from 0 upwards costs O(q |s|). With both at 10^5 that is 10^10 character comparisons.

## The property that saves it

Removing MORE characters can never make p easier to find. If p is not a subsequence after t removals, it is certainly not a subsequence after t + 1, since the surviving string after t + 1 removals is a subsequence of the one after t.

So the values of t that keep p alive are exactly 0, 1, ..., answer, a prefix, and one binary search over t finds the end of it. t = 0 always works because p starts out as a subsequence of s.

## Testing one value of t

Mark the first t positions of the removal order as gone, then walk s once with a pointer into p:

mark = array of |s| falses for i in 0 .. t - 1: mark[order[i]] = true j = 0 for i in 0 .. |s| - 1: if not mark[i] and j < |p| and s[i] == p[j]: j += 1 feasible(t) = (j == |p|)

## Why the greedy subsequence match is correct

The pointer takes the EARLIEST surviving occurrence of each character of p in turn. That is optimal by an exchange argument: suppose some valid embedding of p uses position x for p[0], and the earliest surviving match is at y <= x. Move the first character's match from x to y. The rest of the embedding lies strictly after x, hence strictly after y, so it is still valid. Repeating this for each character in turn turns any embedding into the greedy one, so if an embedding exists the greedy finds one.

This is the same exchange shape as problems 764 and 773: take the earliest legal option, because doing so leaves the largest possible remainder for everything that comes after.

## The bounds

lo = 0 and hi = q. Both ends are legal values of t. Nothing here needs a sentinel, because t = 0 is always feasible by the problem's own guarantee that p is a subsequence of s.

This is the LAST true value, so the midpoint rounds UP and the update is lo = mid.

## The boundary that breaks a careless implementation

The marks must be rebuilt for each candidate t, not accumulated across probes. Binary search does not visit the candidates in increasing order, so a mark array that is only ever added to will be wrong the moment the search steps backwards. Clearing an array of |s| booleans per probe costs O(|s| log q) in total, which is fine.

A neater alternative avoids the clearing entirely: store in when[i] the STEP at which position i is removed, using a large value for positions never removed. Then position i survives t removals exactly when when[i] >= t, and the check needs no array rewriting at all. Both are correct; the second is the one to reach for when the clearing shows up in a profile.

## Overflow

Nothing overflows here: every quantity is bounded by |s| <= 10^5. The problem is in this block for the shape of its predicate, and it is a useful reminder that "binary search on the answer" does not imply "large numbers". What it implies is a monotone yes/no test, and here the test is a string walk.

## Cost

O(|s| log q).

Constraints - `1 ≤ |p| ≤ |s| ≤ 100000` - `s` and `p` contain lowercase English letters only - `p` is a subsequence of `s` - `1 ≤ q ≤ |s|` - the `q` positions are distinct