Find maximum removals from source string

Array Hash Table Two Pointers String Dynamic Programming

39.3% acceptance

Feb 23, 2026

165

You are given a string source of size n, a string pattern that is a subsequence of source, and a sorted integer array targetIndices that contains distinct numbers in the range [0, n - 1]. We define an operation as removing a character at an index idx from source such that: idx is an element of targetIndices. pattern remains a subsequence of source after removing the character. Performing an operation does not change the indices of the other characters in source. For example, if you remove 'c' from "acb", the character at index 2 would still be 'b'. Return the maximum number of operations that can be performed.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_removals(source: String, pattern: String, target_indices: Vec<i32>) -> i32 {
    let s = source.as_bytes();
    let p = pattern.as_bytes();
    let n = s.len();
    let m = p.len();
    
    let is_target: Vec<bool> = {
      let mut t = vec![false; n];
      for &idx in &target_indices {
        t[idx as usize] = true;
      }
      t
    };
    
    // dp[j] = max removals using first j characters of pattern matched so far
    // We iterate through source; for each position:
    // - if it's a target index, we can choose to remove it (skip from pattern matching) or not
    // - if not a target, we must use it if it matches
    let neg_inf = i32::MIN / 2;
    let mut dp = vec![neg_inf; m + 1];
    dp[0] = 0;
    
    for i in 0..n {
      if is_target[i] {
        // Option 1: remove source[i] (contributes +1 to removals, pattern index stays)
        // Option 2: use source[i] for pattern matching (if s[i] == p[j])
        // Process in reverse to avoid using same index twice
        for j in (0..=m).rev() {
          if dp[j] == neg_inf { continue; }
          // Option 1: skip (remove target)
          // dp[j] + 1 is still dp[j] (no pattern advance)
          // We'll update after checking both options
          let remove = dp[j] + 1;
          // Option 2: use for pattern (if matches and j < m)
          if j < m && s[i] == p[j] {
            dp[j + 1] = dp[j + 1].max(dp[j]);
          }
          dp[j] = dp[j].max(remove);
        }
      } else {
        // Must consider using for pattern matching (not removable)
        for j in (0..m).rev() {
          if dp[j] == neg_inf { continue; }
          if s[i] == p[j] {
            dp[j + 1] = dp[j + 1].max(dp[j]);
          }
        }
      }
    }
    
    dp[m].max(0)
  }
}