Maximum Number of Removable Characters - Solution & Explanation
Problem Statement
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 <= 1050 <= removable.length < s.length0 <= removable[i] < s.lengthpis a subsequence ofs.sandpboth consist of lowercase English letters.- The elements in
removableare distinct.
Approach Overview
Problem Overview: You are given a string s, a subsequence target p, and an array removable representing indices in s that can be removed. The goal is to determine the maximum number k such that after removing the first k indices from removable, the string p is still a subsequence of s.
Approach 1: Iterative Validation (O(n * r) time, O(n) space)
Start by removing characters incrementally based on the order in removable. After each removal step, check whether p remains a subsequence of the modified string. The subsequence check uses a classic two pointers scan: one pointer walks through s, the other through p. If characters match, advance both pointers; otherwise only move the pointer on s. Continue until the subsequence condition fails. This approach is straightforward but inefficient because the subsequence validation runs after every removal step, producing worst-case O(n * r) time where n is the length of s and r is the length of removable. Use it when constraints are small or when building intuition for the problem.
Approach 2: Binary Search on Maximum k (O(n log r) time, O(n) space)
The key observation: if removing k characters still keeps p a subsequence, then removing fewer than k characters will also work. This monotonic behavior makes the problem perfect for binary search. Search the range [0, r] to find the largest valid k. For each midpoint k, mark the first k indices in removable as deleted using a boolean array. Then run a subsequence check using two pointers over the string. If p is still a subsequence, move the binary search window right; otherwise move left. Each validation scan costs O(n), and the binary search runs log r iterations, producing an overall complexity of O(n log r).
Recommended for interviews: Binary search with subsequence validation is the expected solution. It demonstrates recognition of monotonic properties and efficient search space reduction. Showing the iterative validation approach first proves you understand the problem mechanics, while the binary search optimization shows algorithmic maturity.
Approach 1: Binary Search on Maximum k
This approach uses binary search to find the maximum number of removable characters 'k' such that 'p' remains a subsequence of 's'. The key idea is to simulate removals and use a helper function to check the subsequence condition within the iteration range dictated by binary search.
The solution initializes a boolean array to keep track of removable characters indices. A binary search is utilized to determine the maximum 'k'. The function isSubsequence checks if 'p' is a subsequence of 's' with 'k' characters removed.
Complexity
Time Complexity: O(n log(m)), where n is the size of 's', and m is the size of 'removable'. The isSubsequence operation runs in O(n), and it is executed log(m) times due to binary search.
Space Complexity: O(n), used for the boolean array to mark characters for removal.
Approach 2: Iterative Validation
This approach removes one character at a time from the removable list and continuously checks if 'p' is a subsequence of 's'. It stops once 'p' is no longer a subsequence.
The iterative C solution attempts to remove one character at a time and checks if the sequence 'p' remains valid. This process is linear without using binary search but depends directly on the removable list's size.
Complexity
Time Complexity: O(n * m), where 'n' is the length of 's' and 'm' is length of the removable array.
Space Complexity: O(n), for the boolean array used for removed indices.
Approach 3: Binary Search
We notice that if removing the characters at the first k indices in removable still makes p a subsequence of s, then removing the characters at k \lt k' leq removable.length indices will also satisfy the condition. This monotonicity allows us to use binary search to find the maximum k.
We define the left boundary of the binary search as l = 0 and the right boundary as r = removable.length. Then we perform binary search. In each search, we take the middle value mid = \left\lfloor \frac{l + r + 1}{2} \right\rfloor and check if removing the characters at the first mid indices in removable still makes p a subsequence of s. If it does, we update the left boundary l = mid; otherwise, we update the right boundary r = mid - 1.
After the binary search ends, we return the left boundary l.
The time complexity is O(k times log k), and the space complexity is O(n). Here, n is the length of the string s, and k is the length of removable.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Kotlin
Complexity Comparison
| Approach | Complexity |
|---|---|
| Binary Search on Maximum k | Time Complexity: O(n log(m)), where n is the size of 's', and m is the size of 'removable'. The isSubsequence operation runs in O(n), and it is executed log(m) times due to binary search. Space Complexity: O(n), used for the boolean array to mark characters for removal. |
| Iterative Validation | Time Complexity: O(n * m), where 'n' is the length of 's' and 'm' is length of the removable array. Space Complexity: O(n), for the boolean array used for removed indices. |
| Binary Search | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Validation | O(n * r) | O(n) | Useful for understanding the subsequence check logic or when input sizes are small. |
| Binary Search on Maximum k | O(n log r) | O(n) | Optimal approach for large inputs where repeatedly validating removals would be too slow. |
Video Solution
Maximum Number of Removable Characters - Binary Search - Leetcode 1898 - Python • NeetCode • 21,731 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Number of Removable Characters easy or hard?
Maximum Number of Removable Characters Python/Java solution
How to solve Maximum Number of Removable Characters in O(n log r)?
What is the best approach for Maximum Number of Removable Characters?
Is Maximum Number of Removable Characters asked at Google/Amazon/Meta?
What data structure is used in Maximum Number of Removable Characters?
What is the time complexity of Maximum Number of Removable Characters?
Ready to solve this problem?
Practice Maximum Number of Removable Characters with our built-in code editor and test cases.
Practice on FleetCode