2430. Maximum Deletions on a String Hard

1/**
2 * [2430] Maximum Deletions on a String
3 *
4 * You are given a string s consisting of only lowercase English letters. In one operation, you can:
5 * 
6 * 	Delete the entire string s, or
7 * 	Delete the first i letters of s if the first i letters of s are equal to the following i letters in s, for any i in the range 1 <= i <= s.length / 2.
8 * 
9 * For example, if s = "ababc", then in one operation, you could delete the first two letters of s to get "abc", since the first two letters of s and the following two letters of s are both equal to "ab".
10 * Return the maximum number of operations needed to delete all of s.
11 *  
12 * Example 1:
13 * 
14 * Input: s = "abcabcdabc"
15 * Output: 2
16 * Explanation:
17 * - Delete the first 3 letters ("abc") since the next 3 letters are equal. Now, s = "abcdabc".
18 * - Delete all the letters.
19 * We used 2 operations so return 2. It can be proven that 2 is the maximum number of operations needed.
20 * Note that in the second operation we cannot delete "abc" again because the next occurrence of "abc" does not happen in the next 3 letters.
21 * 
22 * Example 2:
23 * 
24 * Input: s = "aaabaab"
25 * Output: 4
26 * Explanation:
27 * - Delete the first letter ("a") since the next letter is equal. Now, s = "aabaab".
28 * - Delete the first 3 letters ("aab") since the next 3 letters are equal. Now, s = "aab".
29 * - Delete the first letter ("a") since the next letter is equal. Now, s = "ab".
30 * - Delete all the letters.
31 * We used 4 operations so return 4. It can be proven that 4 is the maximum number of operations needed.
32 * 
33 * Example 3:
34 * 
35 * Input: s = "aaaaa"
36 * Output: 5
37 * Explanation: In each operation, we can delete the first letter of s.
38 * 
39 *  
40 * Constraints:
41 * 
42 * 	1 <= s.length <= 4000
43 * 	s consists only of lowercase English letters.
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/maximum-deletions-on-a-string/
49// discuss: https://leetcode.com/problems/maximum-deletions-on-a-string/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn delete_string(s: String) -> i32 {
55        0
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_2430() {
67    }
68}
69