Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

bablu_45's blog

By bablu_45, history, 7 months ago, ,

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.

• +13

 » 7 months ago, # |   -13 One can use Recursion for this problem
 » 7 months ago, # | ← Rev. 5 →   +6 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)
 » 7 months ago, # | ← Rev. 5 →   +9 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)
•  » » 7 months ago, # ^ |   0 Thanks for the proof.