2565. Subsequence With the Minimum Score Hard

1/**
2 * [2565] Subsequence With the Minimum Score
3 *
4 * You are given two strings s and t.
5 * You are allowed to remove any number of characters from the string t.
6 * The score of the string is 0 if no characters are removed from the string t, otherwise:
7 * 
8 * 	Let left be the minimum index among all removed characters.
9 * 	Let right be the maximum index among all removed characters.
10 * 
11 * Then the score of the string is right - left + 1.
12 * Return the minimum possible score to make t a subsequence of s.
13 * A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "<u>a</u>b<u>c</u>d<u>e</u>" while "aec" is not).
14 *  
15 * <strong class="example">Example 1:
16 * 
17 * Input: s = "abacaba", t = "bzaa"
18 * Output: 1
19 * Explanation: In this example, we remove the character "z" at index 1 (0-indexed).
20 * The string t becomes "baa" which is a subsequence of the string "abacaba" and the score is 1 - 1 + 1 = 1.
21 * It can be proven that 1 is the minimum score that we can achieve.
22 * 
23 * <strong class="example">Example 2:
24 * 
25 * Input: s = "cde", t = "xyz"
26 * Output: 3
27 * Explanation: In this example, we remove characters "x", "y" and "z" at indices 0, 1, and 2 (0-indexed).
28 * The string t becomes "" which is a subsequence of the string "cde" and the score is 2 - 0 + 1 = 3.
29 * It can be proven that 3 is the minimum score that we can achieve.
30 * 
31 *  
32 * Constraints:
33 * 
34 * 	1 <= s.length, t.length <= 10^5
35 * 	s and t consist of only lowercase English letters.
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/subsequence-with-the-minimum-score/
41// discuss: https://leetcode.com/problems/subsequence-with-the-minimum-score/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn minimum_score(s: String, t: String) -> i32 {
47        0
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_2565() {
59    }
60}
61