2472. Maximum Number of Non-overlapping Palindrome Substrings

String Dynamic Programming Greedy Two Pointers Rolling Hash

Problem Overview

You want as many non-overlapping palindromic pieces of length at least k as possible.

Intuition

You want as many non-overlapping palindromic pieces of length at least k as possible. Taking a long palindrome never beats splitting into shorter valid ones, so it is enough to consider endings of length exactly k and k+1. That covers both even and odd centers while keeping the DP cheap.

Algorithm

1Build forward and reverse polynomial hashes of s so any substring palindrome test is O(1).
2Let dp[i] be the best count using only the first i characters.
3Set dp[i] = dp[i-1] (skip the last character).
4If s[i-k .. i-1] is a palindrome, try 1 + dp[i-k].
5If s[i-k-1 .. i-1] is a palindrome, try 1 + dp[i-k-1].
6Return dp[n].

Example Walkthrough

Input: s = "abaccdbbd", k = 3

1.Near the start, "aba" is a length-3 palindrome and can be taken.
2.Later, "dbbd" is a length-4 palindrome of the k+1 form.
3.Those two intervals do not overlap, so the answer reaches 2.

Output: 2

Common Pitfalls

•You do not need every palindrome length; k and k+1 already suffice.
•Guard the k+1 window when the start index would go negative.
•Hash equality is probabilistic; a large modulus and base keep collisions rare for contest constraints.
•dp indexes prefixes by length, so the substring ending at i-1 starts at i-k or i-k-1.

2472.cs

// Approach: Only palindromes of length k or k+1 matter: any longer one
// contains a shorter valid palindrome, which is never worse for maximizing
// count. DP[i] = best using s[0..i). Rolling hashes make each check O(1).
// Complexity: O(n) time and O(n) extra space.
public class Solution
{
    private const long Mod = 1_000_000_007L;
    private const long Base = 131L;

    public int MaxPalindromes(string s, int k)
    {
        int n = s.Length;
        long[] pow = new long[n + 1];
        long[] pref = new long[n + 1];
        long[] suff = new long[n + 1];

        pow[0] = 1;
        for (int i = 0; i < n; i++)
        {
            pow[i + 1] = pow[i] * Base % Mod;
            pref[i + 1] = (pref[i] * Base + s[i]) % Mod;
            suff[i + 1] = (suff[i] * Base + s[n - 1 - i]) % Mod;
        }

        int[] dp = new int[n + 1];
        for (int i = k; i <= n; i++)
        {
            dp[i] = dp[i - 1];
            if (IsPalindrome(pref, suff, pow, n, i - k, i - 1))
                dp[i] = Math.Max(dp[i], 1 + dp[i - k]);
            if (IsPalindrome(pref, suff, pow, n, i - k - 1, i - 1))
                dp[i] = Math.Max(dp[i], 1 + dp[i - k - 1]);
        }

        return dp[n];
    }

    private static bool IsPalindrome(long[] pref, long[] suff, long[] pow, int n, int l, int r)
    {
        if (l < 0)
            return false;
        return GetHash(pref, pow, l, r) == GetHash(suff, pow, n - 1 - r, n - 1 - l);
    }

    private static long GetHash(long[] h, long[] pow, int l, int r)
    {
        long val = (h[r + 1] - h[l] * pow[r - l + 1]) % Mod;
        return val < 0 ? val + Mod : val;
    }
}

Was this solution helpful?