2472.不重叠回文子字符串的最大数目

链接：2472.不重叠回文子字符串的最大数目
难度：Hard
标签：字符串、动态规划
简介：返回最优方案中能选择的子字符串的 最大 数目。

题解 1 - cpp

• 编辑时间：2022-11-13
• 执行用时：44ms
• 内存消耗：6.6MB
• 编程语言：cpp
• 解法介绍：dp[i]表示存在 i 个字符的时候最大回文个数。

class Solution {
public:
    string s;
    int n;
    int maxPalindromes(string s, int k) {
        this->s = s;
        n = s.size();
        vector<int> dp(n + 1, 0);
        for (int i = 0; i < n; i++) {
            check(dp, k, i, i);
            check(dp, k, i, i + 1);
        }
        return dp[n];
    }
    void check(vector<int> &dp, int k, int l, int r) {
        dp[l + 1] = max(dp[l + 1], dp[l]);
        for (; l >= 0 && r < n && s[l] == s[r]; l--, r++) {
            if (r - l + 1 >= k) dp[r + 1] = max(dp[r + 1], dp[l] + 1);
        }
    }
};

题解 2 - cpp

• 编辑时间：2022-11-13
• 执行用时：40ms
• 内存消耗：6.5MB
• 编程语言：cpp
• 解法介绍：方便获取 l 和 r。

class Solution {
public:
    int maxPalindromes(string s, int k) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        for (int i = 0; i < 2 * n - 1; i++) {
            int l = i / 2, r = l + i % 2;
            dp[l + 1] = max(dp[l + 1], dp[l]);
            for (; l >= 0 && r < n && s[l] == s[r]; l--, r++) {
                if (r - l + 1 >= k) dp[r + 1] = max(dp[r + 1], dp[l] + 1);
            }
        }
        return dp[n];
    }
};