You have two strings s and p, where p is a subsequence of s. You also have a distinct array removable containing indices of characters in s (using 0-based indexing).

Your task is to find the maximum number k such that after removing the first k characters indicated by the indices in removable from string s, the string p remains a subsequence of the modified s.

Here's how the removal process works:

• You choose a value k where 0 <= k <= removable.length
• You mark the characters at positions s[removable[0]], s[removable[1]], ..., s[removable[k-1]]
• You remove all marked characters from s
• You check if p is still a subsequence of the remaining string

A subsequence means that p can be formed from s by deleting some (or no) characters without changing the order of the remaining characters.

For example, if s = "abcab", p = "ab", and removable = [0, 1, 2]:

• If k = 0: no removals, p is still a subsequence of s
• If k = 1: remove s[0] ('a'), resulting in "bcab", p is still a subsequence
• If k = 2: remove s[0] and s[1] ('a' and 'b'), resulting in "cab", p is still a subsequence
• If k = 3: remove s[0], s[1], and s[2] ('a', 'b', and 'c'), resulting in "ab", p is still a subsequence

The goal is to find the largest possible k value that maintains p as a subsequence of the modified s.

The key observation is that this problem has a monotonic property: if removing the first k characters from removable still keeps p as a subsequence of s, then removing any fewer characters will also keep p as a subsequence. Conversely, if removing k characters breaks the subsequence relationship, then removing more characters will also break it.

This monotonic behavior creates a sequence of feasibility values:

Removals k:   0    1    2    3    4    5    6
Feasible:     T    T    T    T    F    F    F
                             ↑
                        first_true_index (searching from right)

We want to find the maximum k where p remains a subsequence. Using our standard binary search template, we search for the last true value - the maximum feasible k.

For each candidate k, we define feasible(k) as: after removing characters at indices removable[0] through removable[k-1], is p still a subsequence of s? We check this using two pointers to match characters of p against the non-removed characters of s.

The search range is from 0 (remove nothing) to len(removable) (remove all), and we track the maximum feasible value with first_true_index.

Pattern Learn more about Two Pointers and Binary Search patterns.

The solution uses binary search with the standard template, combined with a subsequence checking function.

Template Structure:

left, right = 0, len(removable)
first_true_index = 0  # Default: we can remove 0 characters

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid  # Record this feasible k
        left = mid + 1          # Try larger k
    else:
        right = mid - 1         # Try smaller k

return first_true_index

The Feasibility Function: For a given value k, we verify if p remains a subsequence of s after removing the first k characters:

1. Create a boolean array to mark which positions are removed
2. Mark positions removable[0] through removable[k-1] as removed
3. Use two pointers to check if p is a subsequence:
   • Pointer i traverses string s
   • Pointer j traverses string p
   • If s[i] is not removed and matches p[j], increment j
   • Always increment i
4. Return True if j == len(p) (all characters matched)

Binary Search Logic:

• If feasible: Record first_true_index = mid and search right (left = mid + 1)
• If not feasible: Search left (right = mid - 1)

Time Complexity: O(n × log m) where n is the length of s and m is the length of removable.

Space Complexity: O(n) for the boolean array.