2472. Maximum Number of Non-overlapping Palindrome Substrings

  • Hardness: \(\color{red}\textsf{Hard}\)
  • Ralated Topics: String、Dynamic Programming
  • \(\color{blue}\textsf{weekly Contest 319}\)

一、題目

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.

Constraints:

  • 1 <= k <= s.length <= 2000
  • s consists of lowercase English letters.

二、分析

  • 動態規劃，定義 dp[i][j] 為索引 i 到索引 j之間的子序列，是否為 palindrome。
    • 當只有兩個字元時，s[i] == s[j] 時為回文。
    • 當大於兩個字元時，除了要滿足 s[i] == s[j] 之外，i+1 到 j-1 的子序列也需為回文，故 dp[i+1][j-1] 需為 true。
  • 注意題目有規定當子序列長度要大於 k 時才可計作解，所以可以設一個值記錄當前最短長度時，滿足題目要求的索引值 pos。

三、解題

1. DP

  • Time complexity: \(O(n^2)\)
  • Space complexity: \(O(n^2)\)
int maxPalindromes(string s, int k) {
    int n = s.length();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int left, right;
    int len = 0;
    int res = 0;
    int pos = 0;
    for (int j = 0; j < n; j++){
        for (int i = 0; i <= j; i++){
            if (i == j){
                dp[i][j] = true;
            } else if (j - i == 1){
                dp[i][j] = s[i] == s[j];
            } else {
                dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);
            }
            if (dp[i][j] && j - i + 1 >= k && i >= pos) {
                pos = j+1;
                res++;
            }
        }
    }
    return res;
}

回目錄 Catalog