2707. Extra Characters in a String Medium

1/**
2 * [2707] Extra Characters in a String
3 *
4 * You are given a 0-indexed string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings.
5 * Return the minimum number of extra characters left over if you break up s optimally.
6 *  
7 * <strong class="example">Example 1:
8 * 
9 * Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
10 * Output: 1
11 * Explanation: We can break s in two substrings: "leet" from index 0 to 3 and "code" from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.
12 * 
13 * <strong class="example">Example 2:
14 * 
15 * Input: s = "sayhelloworld", dictionary = ["hello","world"]
16 * Output: 3
17 * Explanation: We can break s in two substrings: "hello" from index 3 to 7 and "world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.
18 * 
19 *  
20 * Constraints:
21 * 
22 * 	1 <= s.length <= 50
23 * 	1 <= dictionary.length <= 50
24 * 	1 <= dictionary[i].length <= 50
25 * 	dictionary[i] and s consists of only lowercase English letters
26 * 	dictionary contains distinct words
27 * 
28 */
29pub struct Solution {}
30
31// problem: https://leetcode.com/problems/extra-characters-in-a-string/
32// discuss: https://leetcode.com/problems/extra-characters-in-a-string/discuss/?currentPage=1&orderBy=most_votes&query=
33
34// submission codes start here
35
36impl Solution {
37    pub fn min_extra_char(s: String, dictionary: Vec<String>) -> i32 {
38        0
39    }
40}
41
42// submission codes end
43
44#[cfg(test)]
45mod tests {
46    use super::*;
47
48    #[test]
49    fn test_2707() {
50    }
51}
52