383. Maximum Number of Non-overlapping Palindrome Substrings

Any palindrome of length >= k can be shrunk symmetrically from both ends to a palindrome of length exactly k or k+1, and shrinking only frees up room. So it is always enough to consider palindromes of length k or k+1; scan end positions left to right and let dp[i] be the best answer for the prefix s[0..i).

Key observation

We never need to keep a long palindrome. Take any palindrome of length L >= k. Peel off one matching character from each end: the result is still a palindrome, its length drops by 2, and it now covers a smaller range — which can only leave more room for other substrings. Repeat until the length is exactly k (if L and k have the same parity) or k + 1 (otherwise).

Conclusion: an optimal answer can always be built out of palindromes whose length is exactly k or k + 1. That turns an intractable search into a simple prefix DP.

The DP

Let dp[i] = the maximum number of valid non-overlapping palindromes we can pick from the prefix s[0..i) (the first i characters).

• Base: dp[0] = 0 (empty prefix).
• Transition for each end index i (0-based), writing to dp[i+1]):
  • Skip s[i]: dp[i+1] = dp[i].
  • End a palindrome at i: for L in {k, k+1}, let j = i - L + 1. If j >= 0 and s[j..i] is a palindrome, we may take it and add it to the best answer for everything before it: dp[i+1] = max(dp[i+1], dp[j] + 1).
• Answer: dp[n].

Because each transition only ever adds one palindrome on top of dp[j] (a strictly earlier, non-overlapping prefix), overlaps are impossible and the count is always valid.

Worked example

s = "abaccdbbd", k = 3, so we check substrings of length 3 and 4 ending at each index.

dp[9] = 2 — we pick aba (indices 0–2) and dbbd (indices 5–8), matching the expected answer.

Complexity

• Time: O(n * k) — for each of the n end positions we test two candidate substrings, each palindrome check costing O(k). With n <= 2000 this is comfortably fast.
• Space: O(n) for the dp array.

class Solution {
    public int maxPalindromes(String s, int k) {
        int n = s.length();
        // dp[i] = max non-overlapping palindromes (each length >= k) in s[0..i)
        int[] dp = new int[n + 1];
        for (int i = 0; i < n; i++) {
            dp[i + 1] = dp[i]; // option 1: skip s[i]
            // A palindrome of length >= k shrinks to length exactly k or k+1,
            // so only those two candidates ending at index i need checking.
            for (int length = k; length <= k + 1; length++) {
                int j = i - length + 1;
                if (j >= 0 && isPalindrome(s, j, i)) {
                    dp[i + 1] = Math.max(dp[i + 1], dp[j] + 1);
                }
            }
        }
        return dp[n];
    }

    private boolean isPalindrome(String s, int lo, int hi) {
        while (lo < hi) {
            if (s.charAt(lo) != s.charAt(hi)) return false;
            lo++;
            hi--;
        }
        return true;
    }
}