2405. Optimal Partition of String Medium

1/**
2 * [2405] Optimal Partition of String
3 *
4 * Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.
5 * Return the minimum number of substrings in such a partition.
6 * Note that each character should belong to exactly one substring in a partition.
7 *  
8 * Example 1:
9 * 
10 * Input: s = "abacaba"
11 * Output: 4
12 * Explanation:
13 * Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
14 * It can be shown that 4 is the minimum number of substrings needed.
15 * 
16 * Example 2:
17 * 
18 * Input: s = "ssssss"
19 * Output: 6
20 * Explanation:
21 * The only valid partition is ("s","s","s","s","s","s").
22 * 
23 *  
24 * Constraints:
25 * 
26 * 	1 <= s.length <= 10^5
27 * 	s consists of only English lowercase letters.
28 * 
29 */
30pub struct Solution {}
31
32// problem: https://leetcode.com/problems/optimal-partition-of-string/
33// discuss: https://leetcode.com/problems/optimal-partition-of-string/discuss/?currentPage=1&orderBy=most_votes&query=
34
35// submission codes start here
36
37impl Solution {
38    pub fn partition_string(s: String) -> i32 {
39        0
40    }
41}
42
43// submission codes end
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48
49    #[test]
50    fn test_2405() {
51    }
52}
53