maybe it will be useful (or at least interesting) for somebody.

at first i tried to make simple DP with O(n^3).
i tried in java (and i received TLE in 32th test).

after that i tried to realize greed algorithm and understood that this idea is wrong (simple antigreed test is: "abzzbbbzza")

aand finally i've made O(n^2) DP.
little hint: try to precalc d[l][r]:
 d[l][r] = true, s[l..r] - palindrom
 d[l][r] = false, s[l..r] - not palindrom

whats the ans for 'abzzbbbzza'?

4
a b zzbbbzz a

i didn't get it how it will become n^2  because for l=1 to l=n  is one loop and for r=l to r=n is inside loop and for    checking it is palindrome is another loop    so i don't get how it will be n^2 can you please explain me


i am very confused here please help me