25
1
Your task is to determine how much of a perfect palindrome a string is. Your typical palindrome (eg 12321) is a perfect palindrome; its perfectness is 1.
To determine the perfectness of a string, you see how many sections you can split it into where each section is a palindrome. If there are ambiguities, such as with aaaa
, as you can split it into [aa, aa]
or [aaaa]
or [a, aaa]
or [aaa, a]
, the shortest set will override, giving aaaa
a score of 1, which is the length of the shortest set.
Therefore, you must write a program or function that will take one non-empty input and output how perfect it is (which is the length of the shortest set you can split it into where each element in the set is a palindrome).
Examples:
1111 -> 1 [1111]
abcb -> 2 [a, bcb]
abcbd -> 3 [a, bcb, d]
abcde -> 5 [a, b, c, d, e]
66a -> 2 [66, a]
abcba-> 1 [abcba]
x -> 1 [x]
ababacab -> 2 [aba, bacab]
bacababa -> 2 [bacab, aba]
26600 -> 3 [2, 66, 00] [my user id] [who has a more perfect user id?]
ababacabBACABABA -> 4 [aba, bacab, BACAB, ABA]
Note that in the examples anything in square brackets shouldn't be part of the output.
Is the empty string a valid input, and if so, what should the output be? – Zgarb – 2017-04-24T13:09:49.360
8
ababacab
and its reverse,bacababa
, seem to be good test cases. – Neil – 2017-04-24T13:37:53.807@Neil as well as good arguments as to whether a linear-time algorithm is possible. – Leaky Nun – 2017-04-24T13:46:42.467
@Zgarb Empty string is not valid input. – Okx – 2017-04-24T14:54:58.203
ababacabBACABABA
is also a good test case (some answers fail on it). – Zgarb – 2017-04-25T07:43:59.310ababacabBACABABA
has a palindromeababa
– MilkyWay90 – 2019-03-16T21:06:26.993@MilkyWay90 Yes, but it would be longer as you have to do [ababa, c, a, b, BACAB, ABA] which has length 6 – Okx – 2019-03-18T18:47:23.870
@Okx Oh wait, nevermind. I misread something in the rules – MilkyWay90 – 2019-03-18T23:40:02.123