### YouKn0wWho's blog

By YouKn0wWho, 4 months ago, ,

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.

1<=n<=100000

### Example:

aabaa

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.

•
• +12
•

 » 4 months ago, # |   +39 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.
•  » » 4 months ago, # ^ |   +26 The algirithm is desribed in the following work: EERTREE: An Efficient Data Structure for Processing Palindromes in Strings.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 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.
 » 4 months ago, # |   0 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!