Maximum number of removable characters

Array Two Pointers String Binary Search

46.9% acceptance

Feb 25, 2026

1049

137

Given strings s and p (p is a subsequence of s) and array removable, choose maximum k such that after removing s[removable[0..k]], p is still a subsequence of s.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_removals(s: String, p: String, removable: Vec<i32>) -> i32 {
    let s: Vec<u8> = s.into_bytes();
    let p: Vec<u8> = p.into_bytes();
    let n = s.len();

    let is_subseq = |k: usize| -> bool {
      let mut removed = vec![false; n];
      for &r in &removable[..k] {
        removed[r as usize] = true;
      }
      let mut j = 0;
      for i in 0..n {
        if !removed[i] && j < p.len() && s[i] == p[j] {
          j += 1;
        }
      }
      j == p.len()
    };

    let mut lo = 0usize;
    let mut hi = removable.len();
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      if is_subseq(mid) {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    lo as i32
  }
}