2472. Maximum Number of Non-overlapping Palindrome Substrings

The move that makes this problem collapse: whenever a palindrome first reaches length k, cut it there and never look at a longer palindrome with the same center. My first instinct was a full interval DP over every palindromic substring s[j..i] — for each end i, scan all starts j, test the palindrome, and relax dp[i+1] = max(dp[i+1], dp[j]+1). That works but it's O(n^2) palindrome checks stacked on the DP, and it does a lot of pointless work: extending a valid palindrome only eats more characters for the same +1, so a greedy shortest cut always dominates.