Scale Engineer

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
Two Pointers
Algorithms
Binary Search
Data structures
ArrayString
Companies
SnowflakeMoveworks

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 <= 105
  • 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.

class Solution {    public int maximumRemovals(String s, String p, int[] removable) {        // k=0 is always possible. We check for k=1, k=2, ...        for (int k = 1; k <= removable.length; k++) {            boolean[] removed = new boolean[s.length()];            // Mark first k indices as removed            for (int i = 0; i < k; i++) {                removed[removable[i]] = true;            }                        if (!isSubsequence(s, p, removed)) {                // If removing k characters fails, the max was k-1                return k - 1;            }        }                // If we can remove all characters in `removable` and p is still a subsequence        return removable.length;    }     private boolean isSubsequence(String s, String p, boolean[] removed) {        int i = 0; // pointer for s        int j = 0; // pointer for p        while (i < s.length() && j < p.length()) {            if (!removed[i] && s.charAt(i) == p.charAt(j)) {                j++;            }            i++;        }        return j == p.length();    }}

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.

Solutions

boolean 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 ; }

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 →

Next problem