I am stuck on this following problem:
Statement:
Given a string of size n, for each i from 1 to n you need to find if the string can be split into i non-empty non-intersecting palindromes. Output YES/NO.
Constraints:
1<=n<=100000
Example:
Input:
aabaa
Output:
YES
NO
YES
YES
YES
Explanation
aabaa(1 palindrome), aa|b|aa(3 palindromes), a|b|a|aa(4 palindromes), a|b|a|a|a(5 palindromes)
Notice that you can not split the string into 2 palindromes.
Trivia:
Thanks for reading the problem. It will be really helpful if you can provide me with a solution.
Notice that if we can split a string into X palindromes, we can also split it into X+2 palindromes. That's because we can choose a random palindromic substring and split it into 3 parts — 1st character, last character and middle substring. Each of the 3 parts will be palindromic. This means that if we find the least odd and even X such that we can split the string into X palindromes we will have the solution.
Let's have dp[i][parity of X] = minimum possible X such that we can split [1; i] into X palindromic substrings. Computing this dp is almost the same as finding the minimum X without considering parity, which is the well-known problem for finding the minimum palindromic factorization. It can be solved in different ways but the easiest way is with palindromic tree. If you google "minimum palindromic factorization" it will be one of the first results.
The algirithm is desribed in the following work: EERTREE: An Efficient Data Structure for Processing Palindromes in Strings.
I was thinking of how to solve min palindrome factorization using palindromic tree. How do you make use of suffix links to accumulate minimum of dp values. Can you give a brief about it.
Thanks radoslav11 and feodorv for helping me out. Finally, I have solved the problem. This is the solution to the problem I have stated in the blog. I have commented out some sections so that someone can get help from my code.
Happy Coding!