Expert.
Put your skills to the test.

Problem summary

Insert as few separators as possible between letters so every resulting nonempty substring is a palindrome.

Constraints

1 ≤ string length < 10000.

Worked example

Official sample; other valid outputs may exist.

abbabab

1

Solution analysis

1. Let dp[r+1] be the minimum number of palindrome pieces covering the prefix through position r. For every palindromic interval [l,r], update it with dp[l]+1. The answer is the number of pieces minus one.
2. Maintain one Boolean array: before processing r, pal[l] describes whether [l,r−1] is a palindrome. Process l upward and replace pal[l] by s[l]==s[r] and (r−l<2 or old pal[l+1]). The needed old value is still intact because its index is larger.
3. For abbabab, interval abba covers the first four letters and bab covers the last three. The recurrence reaches two pieces, so exactly one cut suffices.

Why it works

A substring is palindromic exactly when its ends match and its interior is empty, one letter, or a palindrome. The in-place update therefore enumerates precisely the palindromes ending at r. Every optimal prefix partition has a final palindromic piece [l,r]; minimizing dp[l]+1 over all such pieces considers it, and each candidate is a valid partition. Induction proves the DP and the final answer.

Watch out. Update pal in increasing left-index order. Separators equal pieces minus one.

An independently written complete program with standard headers.

// Key idea: A substring is palindromic exactly when its ends match and its interior is empty, one
// letter, or a palindrome. The in-place update therefore enumerates precisely the palindromes ending
// at r.
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin>>s;
    int n=static_cast<int>(s.size());
    vector<unsigned char>pal(n+1,0);
    vector<int>dp(n+1,n+1);
    dp[0]=0;
    for(int r=0;r<n;++r){
        for(int l=0;l<=r;++l){
            pal[l]=s[l]==s[r]&&(r-l<2||pal[l+1]);
            if(pal[l]){
                dp[r+1]=min(dp[r+1],dp[l]+1);
            }
        }
    }
    cout<<dp[n]-1<<'\n';
}