Maximum Number Of Removable Characters - Leetcode Solution

Problem:

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_0, s_1, ..., s_{k-1}).

You want to choose an integer k (0 <= k <= removable.length) and remove the k characters at indices removable[0], removable[1], ..., removable[k-1] from s to obtain a new string p'. The order of the remaining characters in s is unchanged.

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

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:

s = "abcacb", p = "ab", removable = [3,1,0] Output: 2 Explanation: After removing the characters at indices 3 and 1, "abcacb" becomes "accb". "a<b" is a subsequence of "abcacb", but not a subsequence of "accb". Similarly, "ab" is a subsequence of "abcacb" but not a subsequence of "accb". Hence, the maximum k is 2.

Example 2:

s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6] Output: 1 Explanation: After removing the character at index 3, "abcbddddd" becomes "abcbdddd". "abcd" is a subsequence of both "abcbddddd" and "abcbdddd". Hence, the maximum k is 1.

Example 3:

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. Similarly, if you remove all indices in the array removable, "abc" is also no longer a subsequence. Hence, the maximum k is 0.

Solution:

To solve this problem, we can use a binary search on the range [0, n - 1], where n is the length of the string s. We can check if a given k is valid by transforming s by removing up to k characters at removable[i] for i in range(k), and then checking if p is a subsequence of the transformed string. We can use a set to store the indices of the characters to be removed, and then iterate over the indices of s and check if the current index is in the set of removed indices. If it is, we skip the current iteration. Otherwise, we compare the current character with the next character in p and if they match, we move to the next character in p. If we can traverse p completely, then p is a subsequence of s with the chosen k characters removed, and k is a valid choice.

We can implement a binary search on the range [0, n - 1] as follows:

• Initialize left to 0 and right to n - 1.
• While left is less than or equal to right, compute mid as (left + right) // 2.
• Create a set to store the indices of the characters to be removed and add removable[i] to the set for i in range(mid + 1).
• Check if p is a subsequence of s with the chosen k characters removed as follows:
  • Initialize i to 0 and j to 0.
  • While i is less than the length of s and j is less than the length of p:
    • If i is in the set of removed indices, increment i and continue to the next iteration of the loop.
    • If s[i] is equal to p[j], increment j.
    • Increment i.
  • If j is equal to the length of p, then p is a subsequence of s with the chosen k characters removed, and k is a valid choice. Update the maximum value of k seen so far and set left to mid + 1 to check for a higher k.
  • Otherwise, p is not a subsequence of s with the chosen k characters removed, and k is not a valid choice. Set right to mid - 1 to check for a lower k.
• Return the maximum value of k seen so far.

The time complexity of this solution is O(n log n), where n is the length of s, due to the binary search, and the space complexity is O(n), due to the set used to store the removed indices.

1