LC-6236.不重叠回文子字符串的最大数目

题目描述

leetcode 困难题

给你一个字符串 s 和一个 正 整数 k 。

从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串：

• 每个子字符串的长度 至少 为 k 。
• 每个子字符串是一个 回文串 。
  返回最优方案中能选择的子字符串的 最大 数目。

子字符串 是字符串中一个连续的字符序列。

字符串之间互不重叠，也就是说对于任意两个子字符串 s[i..j] 和 s[x..y] ，要么 j < x 要么 i > y 。

示例1：

输入：s = "abaccdbbd", k = 3
输出：2
解释：可以选择 s = "abaccdbbd" 中斜体加粗的子字符串。"aba" 和 "dbbd" 都是回文，且长度至少为 k = 3 。
可以证明，无法选出两个以上的有效子字符串。

提示：

提示：
1 <= k <= s.length <= 2000
s 仅由小写英文字母组成

动态规划

我们可以通过两次动态规划得出结果，其中第一次动态规划处理出某个子串 s(i, j) 是否为回文串，第二次动态规划处理如何划分得到最多的不重叠子字符串。

---

第一次 dp，定义 f(i, j) 表示子串 s(i, j) 是否为回文串，那么可以得到转移方程：

f(i, j) = s[i] == s[j]，当 j - i <= 1 时

f(i, j) = f(i + 1, j - 1) && (s[i] == s[j])，当 j - i > 1 时

---

第二次 dp，定义 f(i) 表示 s(0, i) 的最多不重叠回文子串数量，那么 f(n) 为答案。

对于某个 f(i)，可以分两种情况讨论：

如果 s[i] 不在任意回文子串内的话，那么 f(i) = f(i - 1)，可以作为 f(i) 的初始值。

如果 s[i] 在某个回文子串内时，枚举左端点 left，可以得到：
当 s(left, i) 为回文串，f(i) = Max(f(i), f(left - 1) + 1)，其中left 取值范围为 i - left + 1 >= k

class Solution {
    public int maxPalindromes(String s, int k) {
        int n = s.length();
        char[] c = s.toCharArray();
        boolean[][] g = new boolean[n + 1][n + 1];
        for(int i = n + 1; i >= 1; i--){
            for(int j = i; j < n + 1; j++){
                if(c[i - 1] == c[j - 1] && (j - i <= 1 || g[i + 1][j - 1])){
                    g[i][j] = true;
                }
            }
        }
        int[] f = new int[n + 1];
        for(int i = 1; i < n + 1; i++){
            f[i] = f[i - 1]; // i不参与
            for(int left = i - k + 1; left >= 1; left--){
                if(g[left][i]){
                    f[i] = Math.max(f[i], f[left - 1] + 1);
                }
            }
        }
        return f[n];
    }