Normal palindrome is defined as a string that reads the same backwards as forwards, for example "abccba". Chunked palindrome is defined as a string that you can split into chunks and it will form a palindrome. For example, "volvo". You can split it into (vo)(l)(vo). Let A = "vo", B = "l", so the original string is ABA which is a palindrome.
Given a string str, find the maximum number of chunks we can split that string to get a chuncked palindrome.
For eg
:- "aaaaaa", output is 6 ((a)(a)(a)(a)(a)(a))
:- "volvol" output is 2 ((vol)(vol))
Length of string <=2*(10^4)
I can think of a greedy way to solve this problem but not able to prove if it's optimal.
Isn't it simple dynamic programming problem?
$$$n$$$ is length of our string. Let's make dp[L] -- maximum number of chuncks we can split s[L:n-L] (excluding n-L index). We have to examine only such strings, because if we chuncked some part from begin, we should chunk the same part from end.
Base is obvious -- one letter part can be chuncked only to itself (with answer 1), for empty string answer is 0.
Transition: first of all, we can do nothing, so the minimal answer is 1 and it is always possible. After that we can examine all the prefixes if they can be chunked (for that we have to check if s[L:L+i]==s[n-L-i:n-L]). If so, relax answer with 2+dp[L+i].
Be careful with $$$i$$$ limits in a cycle!
To check equality of strings in $$$\mathcal{O}(1)$$$ time you can use hashes or simple LCP dynamic algorithm (as far dynamic already takes $$$n$$$ squared time, one more $$$n$$$ squared wouldn't change assymptotics and LCP is easier to write)
Oh, greedy solution seems to work too.
Here is a proof:
Let's imagine that exists more optimal than greedy split. We will take the best one and will show that we can make better answer that will lead to contradiction.
Let it be $$$a_1$$$$$$a_2$$$$$$a_3$$$$$$\dots$$$$$$a_3$$$$$$a_2$$$$$$a_1$$$
And greedy split is $$$c_1$$$$$$c_2$$$$$$\dots$$$$$$c_2$$$$$$c_1$$$
Lets find minimal $$$i$$$ such that $$$a_i$$$ != $$$c_i$$$ (why such exists is a simple exercise for a reader :))
As far as our algorithm is greedy, then |$$$c_i$$$| < |$$$a_i$$$|. So $$$a_i$$$ can be presented as $$$c_i$$$$$$b$$$. As far as greedy presentation is correct, $$$a_i$$$ ends with $$$c_i$$$. If $$$b$$$ ends with $$$c_i$$$ then $$$a_i$$$ can be presented as $$$c_i$$$$$$d$$$$$$c_i$$$, and instead of $$$a_i$$$$$$\dots$$$$$$a_i$$$ we could use ($$$c_i$$$)($$$d$$$)($$$c_i$$$)$$$\dots$$$($$$c_i$$$)($$$d$$$)($$$c_i$$$) that leads to contradiction.
Now all we need is to proof that $$$b$$$ ends with $$$c_i$$$. Assume the opposite. Then end of first occurence $$$c_i$$$ in $$$a_i$$$ collides with start of last occurence. So start and end of $$$c_i$$$ are equal and this equal part is smaller than $$$c_i$$$. Then remember that our algorithm is greedy. Then it had to take this equal part while splitted $$$c_i$$$$$$\dots$$$$$$c_i$$$ but didn't. Contradiction.
(it is easier to understand if you draw it)