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.

c++

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();
    }
};