Everything is still a Palindrome

Every string is made up of palindromes. For example, the string papaya can be formed in the following way :

1
2
3
pap + aya
p + apa + y + a
p + a + p + a + y + a

We need at least two palindromes to form papaya = pap + aya. This file contains a string of length 1000. What is the minimum number of palindromes do we need to construct the string?

Here are 4 sample inputs and their corresponding output for clarification.

Sample Input

1
2
3
4
abc
abcb
abcba
abcbacabcb

Sample Output

1
2
3
4
3
2
1
2

This is a follow-up of this problem.

×

Problem Loading...

Note Loading...

Set Loading...