YouKn0wWho's blog

By YouKn0wWho, 6 years ago, In English

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.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +39 Vote: I do not like it

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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like 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!