3316. Find Maximum Removals From Source String Medium

1/**
2 * [3316] Find Maximum Removals From Source String
3 *
4 * You are given a string source of size n, a string pattern that is a <span data-keyword="subsequence-string">subsequence</span> of source, and a sorted integer array targetIndices that contains distinct numbers in the range [0, n - 1].
5 * We define an operation as removing a character at an index idx from source such that:
6 * 
7 * 	idx is an element of targetIndices.
8 * 	pattern remains a <span data-keyword="subsequence-string">subsequence</span> of source after removing the character.
9 * 
10 * 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'.
11 * Return the maximum number of operations that can be performed.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">source = "abbaa", pattern = "aba", </span>targetIndices<span class="example-io"> = [0,1,2]</span>
16 * Output: 1
17 * Explanation:
18 * We can't remove source[0] but we can do either of these two operations:
19 * 
20 * 	Remove source[1], so that source becomes "a_baa".
21 * 	Remove source[2], so that source becomes "ab_aa".
22 * </div>
23 * <strong class="example">Example 2:
24 * <div class="example-block">
25 * Input: <span class="example-io">source = "bcda", pattern = "d", </span>targetIndices<span class="example-io"> = [0,3]</span>
26 * Output: 2
27 * Explanation:
28 * We can remove source[0] and source[3] in two operations.
29 * </div>
30 * <strong class="example">Example 3:
31 * <div class="example-block">
32 * Input: <span class="example-io">source = "dda", pattern = "dda", </span>targetIndices<span class="example-io"> = [0,1,2]</span>
33 * Output: <span class="example-io">0</span>
34 * Explanation:
35 * We can't remove any character from source.
36 * </div>
37 * <strong class="example">Example 4:
38 * <div class="example-block">
39 * Input: <span class="example-io">source = </span>"yeyeykyded"<span class="example-io">, pattern = </span>"yeyyd"<span class="example-io">, </span>targetIndices<span class="example-io"> = </span>[0,2,3,4]
40 * Output: 2
41 * Explanation:
42 * We can remove source[2] and source[3] in two operations.
43 * </div>
44 *  
45 * Constraints:
46 * 
47 * 	1 <= n == source.length <= 3 * 10^3
48 * 	1 <= pattern.length <= n
49 * 	1 <= targetIndices.length <= n
50 * 	targetIndices is sorted in ascending order.
51 * 	The input is generated such that targetIndices contains distinct elements in the range [0, n - 1].
52 * 	source and pattern consist only of lowercase English letters.
53 * 	The input is generated such that pattern appears as a subsequence in source.
54 * 
55 */
56pub struct Solution {}
57
58// problem: https://leetcode.com/problems/find-maximum-removals-from-source-string/
59// discuss: https://leetcode.com/problems/find-maximum-removals-from-source-string/discuss/?currentPage=1&orderBy=most_votes&query=
60
61// submission codes start here
62
63impl Solution {
64    pub fn max_removals(source: String, pattern: String, target_indices: Vec<i32>) -> i32 {
65        0
66    }
67}
68
69// submission codes end
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test_3316() {
77    }
78}
79