Problem Description

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.

Intuition

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 (like k-1, k-2, etc.) will definitely keep p as a subsequence as well. Conversely, if removing k characters breaks the subsequence relationship, then removing more characters (k+1, k+2, etc.) will also break it.

Think of it this way: as we remove more characters from s, we're making it harder and harder for p to remain a subsequence. There's a tipping point where we've removed too many characters and p can no longer be formed from the remaining string.

This monotonic behavior is perfect for binary search. We're essentially looking for the boundary - the maximum value of k where the condition still holds true.

We can visualize this as a sequence of true/false values:

• k=0: TRUE (p is subsequence)
• k=1: TRUE (p is subsequence)
• ...
• k=m: TRUE (p is subsequence)
• k=m+1: FALSE (p is NOT subsequence)
• k=m+2: FALSE (p is NOT subsequence)
• ...

We want to find that last TRUE value, which is m in this case.

For each candidate value of k during our binary search, we need to check if p is still a subsequence after removal. We do this by marking the first k indices from removable as "removed" and then using a two-pointer technique to verify if we can still match all characters of p in order within the non-removed characters of s.

The binary search range is from 0 (remove nothing) to len(removable) (remove all possible characters), and we're looking for the rightmost position where the condition is satisfied.

Learn more about Two Pointers and Binary Search patterns.

Solution Approach

The solution uses binary search combined with a subsequence checking function.

Binary Search Setup: We set up our search boundaries:

• Left boundary l = 0 (minimum removals)
• Right boundary r = len(removable) (maximum possible removals)

The Check Function: For a given value k, we need to verify if p remains a subsequence of s after removing the first k characters indicated by removable:

1. Create a boolean array rem of size len(s) to mark which characters are removed
2. Mark the first k indices from removable as True in the rem array
3. Use two pointers to check if p is a subsequence:
   • Pointer i traverses through string s
   • Pointer j traverses through string p
   • If s[i] is not removed (rem[i] is False) and matches p[j], increment j
   • Always increment i to move through s
4. Return True if we've matched all characters of p (i.e., j == len(p))

Binary Search Process: While l < r:

1. Calculate the middle point: mid = (l + r + 1) >> 1
   • The >> 1 is a bitwise right shift, equivalent to integer division by 2
   • We use (l + r + 1) instead of (l + r) to bias toward the upper half when the range has even length
2. Check if removing the first mid characters still maintains the subsequence:
   • If check(mid) returns True: We can potentially remove more, so update l = mid
   • If check(mid) returns False: We've removed too many, so update r = mid - 1

Why the +1 in (l + r + 1) >> 1? This prevents infinite loops when l and r are adjacent. Without it, if l = 2 and r = 3, then mid = (2 + 3) // 2 = 2, and if the check passes, we'd set l = 2 again, causing an infinite loop. With +1, we get mid = 3, ensuring progress.

The algorithm terminates when l == r, and this value represents the maximum number of removals possible while keeping p as a subsequence of s.

Time Complexity: O(n * log m) where n is the length of string s and m is the length of the removable array. We perform O(log m) binary search iterations, and each check operation takes O(n) time.

Space Complexity: O(n) for the boolean array used in the check function.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Given:

• s = "abcbddddd"
• p = "abcd"
• removable = [3, 2, 1, 4, 5, 6]

Goal: Find the maximum k such that after removing characters at indices removable[0] through removable[k-1] from s, the string p remains a subsequence.

Binary Search Process:

Initial setup: l = 0, r = 6 (length of removable array)

Iteration 1:

• mid = (0 + 6 + 1) >> 1 = 3
• Check if we can remove first 3 elements: removable[0:3] = [3, 2, 1]
• Mark positions 3, 2, 1 as removed in string s:
  • Original: a b c b d d d d d (indices 0-8)
  • Removed: a X X X d d d d d (X marks removed)
  • Actual: a d d d d d
• Check if p = "abcd" is subsequence of "addddd":
  • Match 'a' at position 0 ✓
  • Can't find 'b' ✗
• Result: FALSE, so r = mid - 1 = 2

Iteration 2:

• l = 0, r = 2
• mid = (0 + 2 + 1) >> 1 = 1
• Check if we can remove first 1 element: removable[0:1] = [3]
• Mark position 3 as removed:
  • Original: a b c b d d d d d
  • Removed: a b c X d d d d d
  • Actual: a b c d d d d d
• Check if p = "abcd" is subsequence of "abcddddd":
  • Match 'a' at position 0 ✓
  • Match 'b' at position 1 ✓
  • Match 'c' at position 2 ✓
  • Match 'd' at position 3 ✓
• Result: TRUE, so l = mid = 1

Iteration 3:

• l = 1, r = 2
• mid = (1 + 2 + 1) >> 1 = 2
• Check if we can remove first 2 elements: removable[0:2] = [3, 2]
• Mark positions 3 and 2 as removed:
  • Original: a b c b d d d d d
  • Removed: a b X X d d d d d
  • Actual: a b d d d d d
• Check if p = "abcd" is subsequence of "abddddd":
  • Match 'a' at position 0 ✓
  • Match 'b' at position 1 ✓
  • Can't find 'c' ✗
• Result: FALSE, so r = mid - 1 = 1

Final State:

• l = r = 1
• Binary search terminates

Answer: The maximum k = 1, meaning we can remove at most 1 character (at index 3) while keeping p as a subsequence of s.

The beauty of this approach is that we only needed to check 3 different values of k (1, 2, and 3) instead of all 6 possible values, thanks to binary search exploiting the monotonic property of the problem.

Solution Implementation

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. Incorrect Binary Search Boundary Update

One of the most common mistakes is using the wrong binary search template, particularly with the mid calculation and boundary updates.

Pitfall Code:

# Wrong approach that can cause infinite loop
while left < right:
    mid = (left + right) // 2  # Missing +1
    if is_subsequence_after_removal(mid):
        left = mid  # This can cause infinite loop
    else:
        right = mid - 1

Issue: When left = 2 and right = 3, mid will always be 2, and if the check passes, left stays at 2, creating an infinite loop.

Solution: Use mid = (left + right + 1) // 2 to bias toward the upper half when searching for the maximum valid value.

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

Another pitfall is incorrectly setting the initial range or returning the wrong value.

Pitfall Code:

# Wrong: Using len(removable) - 1 as upper bound
left, right = 0, len(removable) - 1

# Or returning the wrong value
return left + 1  # Wrong adjustment

Issue: The range should be [0, len(removable)] inclusive because we can remove anywhere from 0 to all indices in the removable array.

Solution: Initialize right = len(removable) and return left directly.

3. Inefficient Subsequence Checking

Creating a new string after removals is inefficient and can lead to TLE (Time Limit Exceeded).

Pitfall Code:

def is_subsequence_after_removal(num_removals):
    # Inefficient: Creating new string
    modified_s = ""
    removed_set = set(removable[:num_removals])
    for i in range(len(s)):
        if i not in removed_set:
            modified_s += s[i]
  
    # Then check if p is subsequence of modified_s
    j = 0
    for char in modified_s:
        if j < len(p) and char == p[j]:
            j += 1
    return j == len(p)

Issue: String concatenation in Python creates new strings each time, making this O(n²) for string building alone.

Solution: Use a boolean array to mark removed positions and check subsequence without creating a new string, keeping the time complexity at O(n).

4. Using Set Instead of Boolean Array

While using a set seems intuitive, it can be less efficient for this problem.

Pitfall Code:

def is_subsequence_after_removal(num_removals):
    removed_indices = set(removable[:num_removals])
    s_pointer, p_pointer = 0, 0
  
    while s_pointer < len(s) and p_pointer < len(p):
        if s_pointer not in removed_indices and s[s_pointer] == p[p_pointer]:
            p_pointer += 1
        s_pointer += 1
  
    return p_pointer == len(p)

Issue: Set lookup is O(1) average case but has overhead. For index checking with known bounds, a boolean array is faster and more cache-friendly.

Solution: Use a boolean array for O(1) guaranteed lookup with better cache locality.