1898. Maximum Number of Removable Characters Medium

1/**
2 * [1898] Maximum Number of Removable Characters
3 *
4 * You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed).
5 * 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.
6 * Return the maximum k you can choose such that p is still a subsequence of s after the removals.
7 * 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.
8 *  
9 * Example 1:
10 * 
11 * Input: s = "abcacb", p = "ab", removable = [3,1,0]
12 * Output: 2
13 * Explanation: After removing the characters at indices 3 and 1, "a<s>b</s>c<s>a</s>cb" becomes "accb".
14 * "ab" is a subsequence of "<u>a</u>cc<u>b</u>".
15 * If we remove the characters at indices 3, 1, and 0, "<s>ab</s>c<s>a</s>cb" becomes "ccb", and "ab" is no longer a subsequence.
16 * Hence, the maximum k is 2.
17 * 
18 * Example 2:
19 * 
20 * Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
21 * Output: 1
22 * Explanation: After removing the character at index 3, "abc<s>b</s>ddddd" becomes "abcddddd".
23 * "abcd" is a subsequence of "<u>abcd</u>dddd".
24 * 
25 * Example 3:
26 * 
27 * Input: s = "abcab", p = "abc", removable = [0,1,2,3,4]
28 * Output: 0
29 * Explanation: If you remove the first index in the array removable, "abc" is no longer a subsequence.
30 * 
31 *  
32 * Constraints:
33 * 
34 * 	1 <= p.length <= s.length <= 10^5
35 * 	0 <= removable.length < s.length
36 * 	0 <= removable[i] < s.length
37 * 	p is a subsequence of s.
38 * 	s and p both consist of lowercase English letters.
39 * 	The elements in removable are distinct.
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/maximum-number-of-removable-characters/
45// discuss: https://leetcode.com/problems/maximum-number-of-removable-characters/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn maximum_removals(s: String, p: String, removable: Vec<i32>) -> i32 {
51        0
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_1898() {
63    }
64}
65