# 1898. Maximum Number of Removable Characters

• Time: $O(n\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public: int maximumRemovals(string s, string p, vector& removable) { int l = 0; int r = removable.size() + 1; while (l < r) { const int m = (l + r) / 2; const string removed = remove(s, removable, m); if (isSubsequence(p, removed)) l = m + 1; else r = m; } return l - 1; } private: string remove(const string& s, const vector& removable, int k) { string removed(s); for (int i = 0; i < k; ++i) removed[removable[i]] = '*'; return removed; } bool isSubsequence(const string& p, const string& s) { int i = 0; // p's index for (int j = 0; j < s.length(); ++j) if (p[i] == s[j]) if (++i == p.length()) return true; return false; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public int maximumRemovals(String s, String p, int[] removable) { int l = 0; int r = removable.length + 1; while (l < r) { final int m = (l + r) / 2; final String removed = remove(s, removable, m); if (isSubsequence(p, removed)) l = m + 1; else r = m; } return l - 1; } private String remove(final String s, int[] removable, int k) { StringBuilder sb = new StringBuilder(s); for (int i = 0; i < k; ++i) sb.setCharAt(removable[i], '*'); return sb.toString(); } private boolean isSubsequence(final String p, final String s) { int i = 0; // p's index for (int j = 0; j < s.length(); ++j) if (p.charAt(i) == s.charAt(j)) if (++i == p.length()) return true; return false; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution: def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int: l = 0 r = len(removable) + 1 def remove(k: int) -> str: removed = [c for c in s] for i in range(k): removed[removable[i]] = '*' return ''.join(removed) def isSubsequence(p: str, s: str) -> bool: i = 0 for j, c in enumerate(s): if p[i] == s[j]: i += 1 if i == len(p): return True return False while l < r: m = (l + r) // 2 removed = remove(m) if isSubsequence(p, removed): l = m + 1 else: r = m return l - 1