Maximum Number of Removable Characters

Med

#1732Time: O(R * S), where `R` is `removable.length` and `S` is `s.length`. Let the answer be `K_ans`. The loop runs `K_ans + 1` times. Inside the loop, creating the `removed` array takes `O(k)` and checking the subsequence takes `O(S)`. The total time is `O(K_ans * (K_ans + S))`. In the worst case, `K_ans` is `R`, leading to `O(R * (R+S))`, which simplifies to `O(R*S)` as `R < S`. This is too slow for the given constraints.Space: O(S) to store the `removed` boolean array, where S is the length of string `s`.2 companies

Patterns

Algorithms

Data structures

Companies

Prompt

You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed).

You want to choose an integer k (0 <= k <= removable.length) such that, after removing k characters from s using the first k indices in removable, p is still a subsequence of s. More formally, you will mark the character at s[removable[i]] for each 0 <= i < k, then remove all marked characters and check if p is still a subsequence.

Return the maximum k you can choose such that p is still a subsequence of s after the removals.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Example 1:

Input: s = "abcacb", p = "ab", removable = [3,1,0]
Output: 2
Explanation: After removing the characters at indices 3 and 1, "abcacb" becomes "accb".
"ab" is a subsequence of "accb".
If we remove the characters at indices 3, 1, and 0, "abcacb" becomes "ccb", and "ab" is no longer a subsequence.
Hence, the maximum k is 2.

Example 2:

Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
Output: 1
Explanation: After removing the character at index 3, "abcbddddd" becomes "abcddddd".
"abcd" is a subsequence of "abcddddd".

Example 3:

Input: s = "abcab", p = "abc", removable = [0,1,2,3,4]
Output: 0
Explanation: If you remove the first index in the array removable, "abc" is no longer a subsequence.

Constraints:

1 <= p.length <= s.length <= 10⁵
0 <= removable.length < s.length
0 <= removable[i] < s.length
p is a subsequence of s.
s and p both consist of lowercase English letters.
The elements in removable are distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

This is a straightforward brute-force approach. We want to find the maximum k, so we can test each possible value of k starting from k=1 up to removable.length. For each k, we simulate the removal of the first k characters specified in the removable array. Then, we check if p is still a subsequence of the modified string s. The first time this check fails, we know that the maximum number of characters we could remove was k-1. If the check succeeds for all k, the answer is removable.length.

Algorithm

Since k=0 is always a valid case (as p is initially a subsequence of s), we can start checking from k=1.
Loop k from 1 to removable.length.
Create a boolean array removed of size s.length().
Mark the first k indices from removable as true in the removed array.
Call a helper isSubsequence(s, p, removed).
If isSubsequence returns false, then the maximum k is k-1. Return k-1.
If the loop completes, return removable.length.

Walkthrough

In this approach, we iterate through k from 1 to removable.length. In each iteration, we determine the set of indices to be removed, which are removable[0], ..., removable[k-1]. A boolean array of size s.length() is used to efficiently mark these indices.

A helper function, isSubsequence, is used to perform the check. This function iterates through s and p with two pointers. It advances the pointer for s in each step. If the character s[i] is not marked for removal and matches the current character in p, the pointer for p is also advanced.

If p is found to be a subsequence, the loop continues to the next k. If p is not a subsequence, it means k removals are too many. Since we are iterating k in increasing order, the maximum number of successful removals must be k-1. We can immediately return k-1.

If the loop finishes without returning, it implies that even with removable.length removals, p remains a subsequence. In this case, the answer is removable.length.

1class Solution {2    public int maximumRemovals(String s, String p, int[] removable) {3        // k=0 is always possible. We check for k=1, k=2, ...4        for (int k = 1; k <= removable.length; k++) {5            boolean[] removed = new boolean[s.length()];6            // Mark first k indices as removed7            for (int i = 0; i < k; i++) {8                removed[removable[i]] = true;9            }10            11            if (!isSubsequence(s, p, removed)) {12                // If removing k characters fails, the max was k-113                return k - 1;14            }15        }16        17        // If we can remove all characters in `removable` and p is still a subsequence18        return removable.length;19    }20 21    private boolean isSubsequence(String s, String p, boolean[] removed) {22        int i = 0; // pointer for s23        int j = 0; // pointer for p24        while (i < s.length() && j < p.length()) {25            if (!removed[i] && s.charAt(i) == p.charAt(j)) {26                j++;27            }28            i++;29        }30        return j == p.length();31    }32}

Complexity

Time

O(R * S), where `R` is `removable.length` and `S` is `s.length`. Let the answer be `K_ans`. The loop runs `K_ans + 1` times. Inside the loop, creating the `removed` array takes `O(k)` and checking the subsequence takes `O(S)`. The total time is `O(K_ans * (K_ans + S))`. In the worst case, `K_ans` is `R`, leading to `O(R * (R+S))`, which simplifies to `O(R*S)` as `R < S`. This is too slow for the given constraints.

Space

O(S) to store the `removed` boolean array, where S is the length of string `s`.

Trade-offs

Pros

Conceptually simple and easy to implement.

Cons

Highly inefficient due to repeated computations.
Will result in Time Limit Exceeded (TLE) on larger test cases.

A more efficient approach leverages the monotonic nature of the problem. If removing k characters is possible (i.e., p is still a subsequence), then removing any number of characters fewer than k is also possible. Similarly, if removing k characters is not possible, then removing any number of characters more than k is also not possible. This monotonic property allows us to use binary search on the answer k. The search space for k will be from 0 to removable.length.

Algorithm

Initialize low = 0, high = removable.length, and ans = 0.
While low <= high:
- Calculate mid = low + (high - low) / 2.
- Call a helper function isPossible(mid) to check if p is a subsequence after removing mid characters.
- If isPossible(mid) is true, it's a valid k. Store it (ans = mid) and search for a larger k (low = mid + 1).
- Otherwise, mid is too large. Search for a smaller k (high = mid - 1).
Return ans.

Walkthrough

We perform a binary search on the possible values of k, which range from 0 to removable.length. For each mid value of k in our search, we have a helper function isPossible(k) that checks if p remains a subsequence after removing the first k characters from the removable array.

The isPossible(k) function works similarly to the check in the linear scan approach: it marks the first k indices from removable and then uses a two-pointer scan to verify the subsequence property.

In the binary search loop:

If isPossible(mid) is true, it means we can remove mid characters. This is a potential answer, so we save it. To find the maximum k, we need to see if we can remove even more characters, so we continue our search in the upper half (low = mid + 1).
If isPossible(mid) is false, it means mid is too large. We must reduce the number of removals, so we continue our search in the lower half (high = mid - 1).

The binary search continues until low > high, and the last successfully recorded k is the maximum possible value.

1class Solution {2    public int maximumRemovals(String s, String p, int[] removable) {3        int low = 0;4        int high = removable.length;5        int ans = 0;6 7        while (low <= high) {8            int k = low + (high - low) / 2;9            if (isPossible(s, p, removable, k)) {10                ans = k; // This k is possible, try for more11                low = k + 1;12            } else {13                high = k - 1; // This k is not possible, try for less14            }15        }16        return ans;17    }18 19    private boolean isPossible(String s, String p, int[] removable, int k) {20        boolean[] removed = new boolean[s.length()];21        for (int i = 0; i < k; i++) {22            removed[removable[i]] = true;23        }24 25        int i = 0; // pointer for s26        int j = 0; // pointer for p27        while (i < s.length() && j < p.length()) {28            if (!removed[i] && s.charAt(i) == p.charAt(j)) {29                j++;30            }31            i++;32        }33        return j == p.length();34    }35}

Complexity

Time

O(S * log R), where `R` is `removable.length` and `S` is `s.length`. The binary search performs `O(log R)` iterations. Each iteration calls `isPossible(k)`, which takes `O(k + S)` time. The maximum value of `k` is `R`, so the check is `O(R + S)`. The total complexity is `O((R + S) * log R)`. Since `R < S`, this is often simplified to `O(S * log R)`. This is efficient enough for the given constraints.

Space

O(S) for the `removed` boolean array created inside the `isPossible` function in each iteration of the binary search.

Trade-offs

Pros

Significantly more efficient than the linear scan.
Guaranteed to pass within the time limits.

Cons

Slightly more complex to conceptualize than the brute-force approach.

Solutions

Solution

1boolean check ( int x ) { } int search ( int left , int right ) { while ( left < right ) { int mid = ( left + right + 1 ) >> 1 ; if ( check ( mid )) { left = mid ; } else { right = mid - 1 ; } } return left ; }

1/** * @param {string} s * @param {string} p * @param {number[]} removable * @return {number} */ function maximumRemovals(2  s,3  p,4  removable,5) {6  const str_len = s.length;7  const sub_len = p.length;8  /** * @param {number} k * @return {boolean} */ function isSub(k) {9    const removed = new Set(removable.slice(0, k));10    let sub_i = 0;11    for (let str_i = 0; str_i < str_len; ++str_i) {12      if (s.charAt(str_i) === p.charAt(sub_i) && !removed.has(str_i)) {13        ++sub_i;14        if (sub_i >= sub_len) {15          break;16        }17      }18    }19    return sub_i === sub_len;20  }21  let left = 0;22  let right = removable.length;23  while (left < right) {24    const middle = (left + right) >> 1;25    if (isSub(middle + 1)) {26      left = middle + 1;27    } else {28      right = middle;29    }30  }31  return left;32}

1class Solution {2public:3  int maximumRemovals(string s, string p, vector<int> &removable) {4    int left = 0, right = removable.size();5    while (left < right) {6      int mid = left + right + 1 >> 1;7      if (check(s, p, removable, mid)) {8        left = mid;9      } else {10        right = mid - 1;11      }12    }13    return left;14  }15  bool check(string s, string p, vector<int> &removable, int mid) {16    int m = s.size(), n = p.size(), i = 0, j = 0;17    unordered_set<int> ids;18    for (int k = 0; k < mid; ++k) {19      ids.insert(removable[k]);20    }21    while (i < m && j < n) {22      if (ids.count(i) == 0 && s[i] == p[j]) {23        ++j;24      }25      ++i;26    }27    return j == n;28  }29};

1class Solution:2    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int: def check(k): i = j = 0 ids = set(removable[: k]) while i < m and j < n: if i not in ids and s[i] == p[j]: j += 1 i += 1 return j == n m, n = len(s), len(p) left, right = 0, len(removable) while left < right: mid = (left + right + 1) >> 1 if check(mid): left = mid else: right = mid - 1 return left

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem