Formatted question description: https://leetcode.ca/all/1898.html
1898. Maximum Number of Removable Characters
Level
Medium
Description
You are given two strings s
and p
where p
is a subsequence of s
. You are also given a distinct 0indexed integer array removable
containing a subset of indices of s
(s
is also 0indexed).
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^5
0 <= removable.length < s.length
0 <= removable[i] < s.length
p
is a subsequence ofs
.s
andp
both consist of lowercase English letters. The elements in
removable
are distinct.
Solution
Use binary search. Initially, low = 0
and high = removable.length
. Each time, let mid
be the mean of low
and high
and check whether p
is still a subsequence of s
after removing mid
characters from s
according to removable
. The maximum possible k
can be found in this way.

class Solution { public int maximumRemovals(String s, String p, int[] removable) { int low = 0, high = removable.length; while (low < high) { int mid = (high  low + 1) / 2 + low; if (isPossible(s, p, removable, mid)) low = mid; else high = mid  1; } return low; } public boolean isPossible(String s, String p, int[] removable, int k) { int[] removes = new int[k]; for (int i = 0; i < k; i++) removes[i] = removable[i]; Arrays.sort(removes); StringBuffer sb = new StringBuffer(s); for (int i = k  1; i >= 0; i) sb.deleteCharAt(removes[i]); return isSubsequence(p, sb.toString()); } public boolean isSubsequence(String s, String t) { if (s.length() == 0) return true; if (s.length() > t.length()) return false; int sLength = s.length(), tLength = t.length(); int sIndex = 0, tIndex = 0; while (sIndex < sLength && tIndex < tLength) { char sChar = s.charAt(sIndex), tChar = t.charAt(tIndex); if (sChar == tChar) sIndex++; tIndex++; } return sIndex == sLength; } }

Todo

# 1898. Maximum Number of Removable Characters # https://leetcode.com/problems/maximumnumberofremovablecharacters/ class Solution: def maximumRemovals(self, s: str, p: str, removable: List[int]) > int: n = len(s) pn = len(p) rn = len(removable) def good(x): x = rn  x sset = set(removable[:x]) j = 0 for i, x in enumerate(s): if x == p[j] and i not in sset: j += 1 if j == pn: return True return False left, right = 0, rn while left < right: mid = (left + right) // 2 if good(mid): right = mid else: left = mid + 1 return rn  left