Maximum Deletions on a String

You are given a string s consisting of only lowercase English letters. In one operation, you can:

• Delete the entire string s , or
• 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 \leq i \leq s.length / 2$.
• 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" .

Return the maximum number of operations needed to delete all of  s .

Example 1:

Input: s = "abcabcdabc"
Output: 2
Explanation:
- Delete the first 3 letters ("abc") since the next 3 letters are equal. Now, s = "abcdabc".
- Delete all the letters.
We used 2 operations so return 2. It can be proven that 2 is the maximum number of operations needed.
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.

Example 2:

Input: s = "aaabaab"
Output: 4
Explanation:
- Delete the first letter ("a") since the next letter is equal. Now, s = "aabaab".
- Delete the first 3 letters ("aab") since the next 3 letters are equal. Now, s = "aab".
- Delete the first letter ("a") since the next letter is equal. Now, s = "ab".
- Delete all the letters.
We used 4 operations so return 4. It can be proven that 4 is the maximum number of operations needed.

Example 3:

Input: s = "aaaaa"
Output: 5
Explanation: In each operation, we can delete the first letter of s.

解题思路

　　看到数据范围考虑用dp。

　　定义状态$f(i)$表示删除$[i,n]$这个字符串的所有操作方案的集合，属性是最大值。根据前缀的$j$个字符与后$j$个字符是否相同来划分集合，即如果$[i,i+j-1]$与$[i+j, i+2 \cdot j - 1]$相同，则可以从$f(i+j)$转移到$f(i)$。状态转移方程就是$f(i) = max \{ {f(i+j)+1} \}$，$j$要满足$j \leq \frac{n - i + 1}{2}$。

　　这里判断同一个字符串中两个子串是否相同需要用到字符串哈希，如果用substr来判断的话会超时。一开始忘了这个模型，导致一直TLE。

　　AC代码如下：

 1 typedef unsigned long long ULL;
 2 
 3 const int N = 4010, P = 131;
 4 
 5 ULL h[N], p[N];
 6 
 7 class Solution {
 8 public:
 9     ULL get(int l, int r) {
10         return h[r] - h[l - 1] * p[r - l + 1];
11     }
12     
13     int deleteString(string s) {
14         int n = s.size();
15         p[0] = 1;
16         for (int i = 1; i <= n; i++) {
17             h[i] = h[i - 1] * P + s[i - 1];
18             p[i] = p[i - 1] * P;
19         }
20         
21         vector<int> f(n + 2);
22         for (int i = n; i; i--) {
23             f[i] = 1;   // 全部删除的情况
24             for (int j = 1; i + j + j - 1 <= n; j++) {
25                 if (get(i, i + j - 1) == get(i + j, i + j + j - 1)) f[i] = max(f[i], f[i + j] + 1);
26             }
27         }
28         
29         return f[1];
30     }
31 };

参考资料

　　力扣第313场周赛：https://www.bilibili.com/video/BV16g411a7t6/