LeetCode 解題筆記：2472. Maximum Number of Non-overlapping Palindrome Substrings

作者：王一哲
日期：2026年9月15日


LeetCode 題目連結：2472. Maximum Number of Non-overlapping Palindrome Substrings

解題想法

困難題，題目給一個字串 $s$ 與整數 $k$，要找出 $s$ 之中不重疊且長度至少為 $k$ 的迴文子字串數量。由於字串長度最長為 $1000$，需要先計算所有子字串是否為迴文字串，再用動態規畫找答案。假設 $s$ 的長度為 $n$，先建一個大小為 $n \times n$ 的二維陣列 is_pal，is_pal[i][j] 代表 $s[i...j]$ 是否為迴文字串。接下來再建一個長度為 $n+1$ 的一維陣列 $dp$，$dp[i]$ 代表以 $s[i-1]$ 為結尾時不重疊且長度至少為 $k$ 的迴文子字串數量，預設值皆為 $0$。更新狀態時先取 $dp[i] = dp[i-1]$，再跑起點 $j$ 從 $0$ 到 $i - k$，如果 $s[j ... i-1]$ 是迴文字串，取 $dp[i], dp[j] + 1$ 較大者更新 $dp[i]$。全部跑完之後答案在 $dp[n]$。

Python 程式碼

Runtime: 2230 ms, beats 25.77%. Memory: 50.73 MB, beats 14.43%.

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        # 1. 建表，列出 s[i : j+1] 是否為迴文字串
        is_pal = [[False] * n for _ in range(n)]
        for i in range(n-1, -1, -1):  # 由後往前掃
            is_pal[i][i] = True  # 長度 1，一定是迴文字串
            for j in range(i+1, n):  # 掃過 j = i + 1 ~ j = n - 1
                if s[i] == s[j]:
                    if j == i + 1 or is_pal[i+1][j-1]:  # 長度是 2 或內部也是迴文
                        is_pal[i][j] = True
        
        # 2. 一維 dp，計算 s[:i+1] 不重疊的迴文子字串數量
        dp = [0] * (n + 1)
        for i in range(1, n+1):
            # 不取 s[i-1] 為結尾的子字串
            dp[i] = dp[i-1]
            # 跑起點 j，長度至少為 k
            for j in range(i-k+1):
                if is_pal[j][i-1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return dp[n]

C++ 程式碼

Runtime: 132 ms, beats 58.38%. Memory: 19.62 MB, beats 34.82%.

class Solution {
public:
    int maxPalindromes(string s, int k) {
        int n = (int)s.size();
        /* 1. 建表，列出 s[i : j+1] 是否為迴文字串 */
        vector<vector<bool>> is_pal (n, vector<bool> (n, false));
        for(int i = n-1; i >= 0; i--) {  // 由後往前掃
            is_pal[i][i] = true;  // 長度 1，一定是迴文字串
            for(int j = i+1; j < n; j++) {  // 掃過 j = i + 1 ~ j = n - 1
                if (s[i] == s[j]) {
                    if (j == i+1 || is_pal[i+1][j-1]) {  // 長度是 2 或內部也是迴文
                        is_pal[i][j] = true;
                    }
                }
            }
        }
        
        /* 2. 一維 dp，計算 s[:i+1] 不重疊的迴文子字串數量 */
        vector<int> dp (n+1, 0);
        for(int i = 1; i <= n; i++) {
            dp[i] = dp[i-1];  // 不取 s[i-1] 為結尾的子字串
            // 跑起點 j，長度至少為 k
            for(int j = 0; j <= i - k; j++) {
                if (is_pal[j][i-1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n];
    }
};