2472. Maximum Number of Non-overlapping Palindrome Substrings
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public:
int maxPalindromes(string s, int k) {
string ss = "#";
for(auto a : s) {
ss.push_back(a);
ss.push_back('#');
}
vector<int> dp(ss.length());
int l = 0, r = -1, n = ss.size(), mi = ss.length();
for(int i = 0; i < n; i++) {
dp[i] = max(0, min(r - i, r + l - i >= 0 ? dp[r + l - i] : -1));
while(i + dp[i] < n and i - dp[i] >= 0 and ss[i-dp[i]] == ss[i+dp[i]]) dp[i]++;
if(i + dp[i] == n) mi = min(mi, i - dp[i]);
if(r < i + dp[i]) {
r = i + dp[i];
l = i - dp[i];
}
}
vector<int> dpp(ss.length());
for(int i = 0; i < ss.length(); i++) {
if(dp[i] * 2 + 2 < k) {
if(i) dpp[i] = max(dpp[i], dpp[i-1]);
} else {
int l = i - dp[i] + 1;
int r = i + dp[i] - 1;
int count = 0;
for(int j = l; j <= r; j++) if(ss[j] != '#') count += 1;
for(int j = l, match = r; j <= i and count >= k; j++,match--) {
dpp[match] = max(dpp[match], (j ? dpp[j-1] : 0) + 1);
if(ss[j] != '#') count -= 2;
}
if(i) dpp[i] = max(dpp[i], dpp[i-1]);
}
}
return dpp.back();
}
};
|
