PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
It is clear that K(1)=0. Hence we will only consider L from 2 to N.
Assume that for some L substrings S[1, L] and S[2, L + 1] are palindromes. Then it is easy to see that for even L we must have S[i] = S[i - 1] (1 < i <= L + 1) and for odd L we must have S[i] = S[i - 2] (2 < i <= L + 1). For example, let S[1, 4] and S[2, 5] are palindromes. Then by definition of palindrome we have S 1 = S 4 , S 2 = S 3 , S 1 = S 5 , S 2 = S 4 . From here it follows that all characters of S[1, 5] are equal.
Append some imaginary character to the end of S. Note that now K(L) always exists. But if for some L we obtain that K(L) = N - L + 2 then we should set K(L) = 0.
For d = 1, 2 denote by I[d] the first integer i > d such that s[i] != s[i - d]. For example, for the string “ccccodechef” we have I 1 = 5 and I 2 = 5, for the string “cococodechef” we have I 1 = 2 and I 2 = 7.
Let L be an even integer from 2 to N. If I 1 >= L then it is clear that first non-palindrome substring of length L is S[I[ 1 ] - L + 1, I 1 ] (all previous substring are composed of equal characters but this one has last character that differs from the first). So in this case K(L) = I1 - L + 1. Otherwise let’s check whether the prefix S[1, L] is a palindrome. If it not then K(L) = 1. But if it is a palindrome than by considerations of the second paragraph and definition of I1 we must have that S[2, L + 1] is not a palindrome. So we can set K(L) = 2 even without checking whether S[2, L + 1] is a palindrome.
Now let L be an odd integer from 2 to N. If I 2 >= L then it is clear that first non-palindrome substring of length L is S[I[ 2 ] - L + 1, I 2 ] (all previous substring has the form “aba…aba” but this one has last character that differs from the first). So in this case K(L) = I 2 - L + 1. Otherwise let’s check whether the prefix S[1, L] is a palindrome. If it not then K(L) = 1. But if it is a palindrome than by considerations of the second paragraph and definition of I 2 we must have that S[2, L + 1] is not a palindrome. So we can set K(L) = 2 even without checking whether S[2, L + 1] is a palindrome.
Thus we see that we should only be able to test prefixes of the string by palindrome test. This can easily be done using hashes. Just iterate over prefixes and update in O(1) time polynomial hash of prefix and its reverse. Another approach is to use Z-algorithm here. Append to S its reverse and denote this new string by T. Then prefix S[1, L] is a palindrome if and only if z[2*N - L + 1] = L where z[k] denotes the largest number i such that T[1, i] = T[k, k + i - 1]. Numbers z1, z2, …, z[2 * N] can be calculated in O(N) time by Z-algorithm . You can read about it elsewhere.
Thus we obtain quite simple O(N) algorithm for solving the problem.
There is also another approach possible here. It uses Manacher algorithm for finding palindrome radii and then some greedy considerations allow us to solve the problem in O(N) time. See tester solution as a reference. Instead of Manacher algorithm you can use hashes and binary search to find palindrome radii in O(N log N) time.
SETTER’S SOLUTION
Can be found here.
Problem Setter’s
alternate solution
TESTER’S SOLUTION
Can be found here.