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 <= 2000sconsists 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;
}