Hard

题目描述

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

从字符串 s 中选择一组非重叠的子串，满足以下条件：

  • 每个子串的长度至少为 k。
  • 每个子串都是回文串。

返回在最优选择中子串的最多数目。

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

示例 1：

输入: s = "abaccdbbd", k = 3
输出: 2
解释: 我们可以选择 s = "abaccdbbd" 中带下划线的子串。"aba" 和 "dbbd" 都是回文串且长度至少为 k = 3。
可以证明我们无法找到包含两个以上有效子串的选择。

示例 2：

输入: s = "adbcda", k = 2
输出: 0
解释: 字符串中没有长度至少为 2 的回文子串。

提示：

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

解题思路

解题思路

这是一个经典的动态规划问题，结合贪心策略来求解。

核心思想： 使用动态规划来记录以每个位置结尾时能得到的最大回文子串数量。对于每个位置，我们考虑所有可能的回文子串结尾情况，选择能带来最大收益的方案。

算法步骤：

  1. 预处理回文判断： 使用中心扩展法或动态规划预处理所有子串的回文性质
  2. 状态定义： dp[i] 表示考虑字符串前 i 个字符时能得到的最大回文子串数量
  3. 状态转移： 对于位置 i，我们有两种选择：
    • 不选择以位置 i 结尾的任何回文子串：dp[i] = dp[i-1]
    • 选择一个以位置 i 结尾且长度至少为 k 的回文子串：dp[i] = max(dp[i], dp[j] + 1)，其中 j 是该回文子串的起始位置前一位
  4. 贪心优化： 当找到合法回文子串时，优先选择最早结束的（最短的），这样为后续选择留出更多空间

时间复杂度分析： 预处理回文需要 O(n²)，DP 转移也是 O(n²)，总体 O(n²) 空间复杂度： 需要 O(n²) 存储回文信息和 O(n) 的 DP 数组

代码实现

class Solution {
public:
    int maxPalindromes(string s, int k) {
        int n = s.length();
        vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));
        
        // 预处理所有子串的回文性质
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
        }
        for (int i = 0; i < n - 1; i++) {
            isPalindrome[i][i + 1] = (s[i] == s[i + 1]);
        }
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                isPalindrome[i][j] = (s[i] == s[j]) && isPalindrome[i + 1][j - 1];
            }
        }
        
        vector<int> dp(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1]; // 不选择以 i-1 结尾的回文串
            for (int j = 0; j < i; j++) {
                if (i - j >= k && isPalindrome[j][i - 1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        
        # 预处理所有子串的回文性质
        is_palindrome = [[False] * n for _ in range(n)]
        
        # 单个字符都是回文
        for i in range(n):
            is_palindrome[i][i] = True
        
        # 长度为2的子串
        for i in range(n - 1):
            is_palindrome[i][i + 1] = (s[i] == s[i + 1])
        
        # 长度大于2的子串
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                is_palindrome[i][j] = (s[i] == s[j]) and is_palindrome[i + 1][j - 1]
        
        # 动态规划
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = dp[i - 1]  # 不选择以 i-1 结尾的回文串
            for j in range(i):
                if i - j >= k and is_palindrome[j][i - 1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return dp[n]

public class Solution {
    public int MaxPalindromes(string s, int k) {
        int n = s.Length;
        bool[,] isPalindrome = new bool[n, n];
        
        // 预处理所有子串的回文性质
        for (int i = 0; i < n; i++) {
            isPalindrome[i, i] = true;
        }
        for (int i = 0; i < n - 1; i++) {
            isPalindrome[i, i + 1] = (s[i] == s[i + 1]);
        }
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                isPalindrome[i, j] = (s[i] == s[j]) && isPalindrome[i + 1, j - 1];
            }
        }
        
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1]; // 不选择以 i-1 结尾的回文串
            for (int j = 0; j < i; j++) {
                if (i - j >= k && isPalindrome[j, i - 1]) {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }
        
        return dp[n];
    }
}

var maxPalindromes = function(s, k) {
    const n = s.length;
    const isPalindrome = Array(n).fill().map(() => Array(n).fill(false));
    
    // 预处理所有子串的回文性质
    for (let i = 0; i < n; i++) {
        isPalindrome[i][i] = true;
    }
    for (let i = 0; i < n - 1; i++) {
        isPalindrome[i][i + 1] = (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n²)
空间复杂度O(n²)
  • 时间复杂度：O(n²)，其中 n 是字符串长度。预处理回文子串需要 O(n²)，动态规划转移也需要 O(n²)
  • 空间复杂度：O(n²)，主要用于存储 isPalindrome 数组，DP 数组只需要 O(n) 空间

相关题目