{x}
blog image

Maximum Number of Removable Characters

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.

Solution Explanation: Maximum Number of Removable Characters

This problem asks to find the maximum number of characters we can remove from string s such that string p remains a subsequence of the modified s. The indices of characters to remove are provided in the removable array. A key observation is that if removing the first k characters from removable keeps p as a subsequence, then removing any fewer characters will also maintain this property. This monotonicity allows for a highly efficient solution using binary search.

Approach:

  1. Binary Search: We employ binary search on the removable array's indices (0 to removable.length). The binary search's goal is to find the largest k such that removing the first k characters specified by removable leaves p as a subsequence of s.

  2. check(k) function: This helper function simulates the removal of the first k characters. It creates a boolean array rem to track removed characters. Then, it iterates through s and p simultaneously. If a character in s is not removed (!rem[i]) and matches the current character in p, we move to the next character in p. If we reach the end of p, it means p remains a subsequence.

  3. Binary Search Loop: The binary search iteratively checks the midpoint mid. If check(mid) returns true (meaning p is still a subsequence after removing the first mid characters), we update the lower bound (l = mid) to search for a larger k. Otherwise, we update the upper bound (r = mid - 1).

  4. Return Value: The final value of l after the binary search represents the maximum number of removable characters.

Time Complexity Analysis:

  • Binary Search: The binary search takes O(log k) time, where k is the length of the removable array.
  • check(k) function: The check function iterates through s and p at most once, taking O(n + m) time, where n is the length of s and m is the length of p. Since m ≤ n, the complexity can be simplified to O(n).
  • Overall: The overall time complexity is O(n log k) because the check function is called O(log k) times within the binary search.

Space Complexity Analysis:

The space complexity is dominated by the boolean array rem in the check function, which uses O(n) space. Other variables use constant space. Therefore, the overall space complexity is O(n).

Code Examples (Python, Java, C++, Go, TypeScript, Rust, JavaScript, Kotlin):

The code examples provided in the previous response demonstrate this approach in several programming languages. They all follow the same algorithmic structure: a binary search that calls a check function to verify subsequence existence after removals. Each function's implementation details might vary slightly based on the language's syntax and standard library features but the core logic remains consistent.