Solution Approach

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.

Example Walkthrough

Let's walk through with s = "abcbddddd", p = "abcd", and removable = [3, 2, 1, 4, 5, 6].

Step 1: Initialize

• left = 0, right = 6 (length of removable)
• first_true_index = 0

Step 2: Binary search iterations

Iteration 1: left = 0, right = 6

• mid = (0 + 6) // 2 = 3
• Remove first 3 indices: positions 3, 2, 1
• String becomes: a _ _ _ d d d d d → "addddd"
• Is "abcd" a subsequence? Can match 'a', but can't find 'b' ✗
• Update: right = 3 - 1 = 2

Iteration 2: left = 0, right = 2

• mid = (0 + 2) // 2 = 1
• Remove first 1 index: position 3
• String becomes: a b c _ d d d d d → "abcddddd"
• Is "abcd" a subsequence? Match a→b→c→d ✓
• Update: first_true_index = 1, left = 1 + 1 = 2

Iteration 3: left = 2, right = 2

• mid = (2 + 2) // 2 = 2
• Remove first 2 indices: positions 3 and 2
• String becomes: a b _ _ d d d d d → "abddddd"
• Is "abcd" a subsequence? Match a→b, but can't find 'c' ✗
• Update: right = 2 - 1 = 1

Step 3: Loop terminates

• left = 2 > right = 1
• Return first_true_index = 1

We can remove at most 1 character while keeping p as a subsequence.

Time and Space Complexity

The time complexity is O(k × n × log k), where n is the length of string s and k is the length of removable.

• The binary search performs O(log k) iterations since we're searching in the range [0, len(removable)]
• For each binary search iteration, we call the check function
• The check function:
  • Creates a boolean array rem of size n and marks mid positions: O(n + mid) where mid ≤ k
  • Performs a two-pointer traversal through string s to verify if p is a subsequence: O(n)
  • Overall check function: O(n)
• Total time complexity: O(log k) × O(n) = O(n × log k)

However, the reference answer states O(k × log k). This appears to be considering a different perspective or possibly an error. The actual complexity should be O(n × log k) based on the code analysis.

The space complexity is O(n), where n is the length of string s.

• The rem boolean array in the check function uses O(n) space
• Other variables use constant space
• Total space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using the Wrong Binary Search Template

The Pitfall: Using while left < right with left = mid instead of the standard while left <= right template.

Why It Happens: The left < right with left = mid variant requires mid = (left + right + 1) // 2 to avoid infinite loops. The standard template is simpler and less error-prone.

Solution: Use the standard template:

left, right = 0, len(removable)
first_true_index = 0

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        left = mid + 1
    else:
        right = mid - 1

return first_true_index

2. Off-by-One Error in Binary Search Range

The Pitfall: Using len(removable) - 1 as upper bound.

Solution: The range should be [0, len(removable)] because we can remove 0 to all indices.

3. Inefficient Subsequence Checking

The Pitfall: Creating a new string after removals.

Solution: Use a boolean array to mark removed positions and check subsequence in-place:

is_removed = [False] * len(s)
for i in range(k):
    is_removed[removable[i]] = True