Maximum Number of Non-overlapping Palindrome Substrings、

You are given a string s and a positive integer k .

Select a set of non-overlapping substrings from the string s that satisfy the following conditions:

• The length of each substring is at least k .
• Each substring is a palindrome.

Return the maximum number of substrings in an optimal selection.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "abaccdbbd", k = 3
Output: 2
Explanation: We can select the substrings underlined in s = "abaccdbbd". Both "aba" and "dbbd" are palindromes and have a length of at least k = 3.
It can be shown that we cannot find a selection with more than two valid substrings.

Example 2:

Input: s = "adbcda", k = 2
Output: 0
Explanation: There is no palindrome substring of length at least 2 in the string.

解题思路

　　主要记录用dp的方法求回文子串。比赛的时候是枚举回文子串的中心然后往两边扩展来求的。

　　定义$f(i, j)$表示区间$[i, j]$内的字符串是否为回文串。状态转移的话，如果有$s_i = s_j$并且区间$[i+1, j-1]$内的字符串为回文串，那么区间$[i, j]$就是回文串。

　　然后定义$g(i)$表示前$i$个位置所有选择回文串的方案，属性是回文串的最大值。根据后缀所选择的回文串的长度来进行集合的划分。

　　AC代码如下：

 1 class Solution {
 2 public:
 3     int maxPalindromes(string s, int k) {
 4         int n = s.size();
 5         vector<vector<bool>> f(n + 1, vector<bool>(n + 1));
 6         for (int len = 1; len <= n; len++) {
 7             for (int i = 1; i + len - 1 <= n; i++) {
 8                 int j = i + len - 1;
 9                 if (len == 1) f[i][j] = true;
10                 else if (s[i - 1] == s[j - 1] && (len == 2 || f[i + 1][j - 1])) f[i][j] = true;
11             }
12         }
13         vector<int> g(n + 1);
14         for (int i = 1; i <= n; i++) {
15             g[i] = g[i - 1];    // 后缀不选择回文串
16             for (int j = i - k + 1; j >= 1; j--) {
17                 if (f[j][i]) g[i] = max(g[i], g[j - 1] + 1);    // 后缀选择s[j~i]这个回文串
18             }
19         }
20         return g[n];
21     }
22 };

参考资料

　　力扣第319场周赛：https://www.bilibili.com/video/BV1kY411Z7uE/