PALIN3 - Editorial



Author: Konstantin Sokol
Tester: Gerald Agapov
Editorialist: Tasnim Imran Sunny




Manacher’s Algorithm


Given a string S which is consisted of only digits, find the number of palindromic substrings of S without leading zeros and is divisible by 3.


Consider counting all odd length palindromes.

Let D[i] = the length of longest palindromic substring centering at index i.
So if S=”ababac” D would be {1,3,5,3,1,1}. This table D[] can be computed in linear time using Manacher’s algorithm. You can read how to implement Manacher’s algorithm here or here.

Remember that if a number is divisible by 3, the total sum of all of it’s digits is divisible by 3.

Let C(i,j) = The sum of digits between i and j (inclusive) = Si + Si+1 + … + Sj

For each index i compute the number of odd length palindromic substrings centering i and which are divisible by 3. Let, l = (D[i] – 1)/2. So, Si-k … Si … Si+k would be palindrome centering i where 1 <= k <= l . The sum of digits of left and right of i of the palindrome would be same. Let the sum of digits of one side be x, so to be divisible by 3:

( Si + 2*x) mod 3 = 0

Since everything is considered modulo 3, it’s enough to find the reminder of x modulo 3, instead of the sum. So x could have values 0,1 or 2 and the above equation can be solved easily by trying every value.
So the number of palindromes divisible by 3 centering i would be same as the number of k’s(1 <= k <= l) where C(i+1, i+k) mod 3 = x.
This can be found easily in constant time with linear precomputation.
To find that, for each value of y (0 <= y <= 2) and index i precompute how many indexes between 1 and i have C(1,i) mod 3 = y . Since it’s a palindrome, if a number contains a leading zero then it contains a trailing zero too,so only the indexes i where Si != 0 are considered in the precomputation.

The even length palindromes can be counted similarly.

The complexity of the solution is O(N).


Author’s solution can be found here.
Tester’s solution can be found here.


Too bad my hashing+binsearch algorithm on longest palindrome centered at i didn’t fit in the time limit. It probably would’ve if the time limit was 2 seconds instead of 1.

More precisely, just why did I have to waste an hour optimizing my code? There was better stuff to do. Anything was better stuff to do…

Well, at least I see that Manacher can actually be useful in a contest sometimes. Up till now, I thought my hash+binsearch variation would always work.


It seems that binary search+hashing passed all tests in time limit. It was first attempt now. My solution: CodeChef: Practical coding for everyone

I also implemented hashing+binsearch and got AC. But I had to optimize my initial implementation in order to get AC (which cost me both time + several TLE attempts). In case you’re interested, the last optimization which got me AC was to use a separate unordered_map for each palindrome length (instead of a single unordered_map in which I would store the hashes of all the palindromes, as I did in my initial submissions).

" To find that, for each value of y (0 <= y <= 2) and index i precompute how many indexes between 1 and i have C(1,i) mod 3 = y "

Can anyone tell me why ?

We will apply manacher algo first as usual. Lets consider odd length palindromes.
Let x be the sum of digits to the right of i which forms palindrome centered at i. Total sum of palindrome will be 2x+s[i]. So, (2x+s[i])%3 == 0.
By trial and error you can see if x%3 == s[i]%3, then (2*x+s[i])%3 = 0.

Let the palindrome be s[i-k…i…i+k]. We need to find the ans[i] = no of k such that k<=d[i] and sum[i+1…k]%3 = s[i]%3. To to this we will precompute sum[i] and cnt[i][y] in linear time.
sum[i] is sum of digits till i mod 3.
cnt[i][y] = no of k such that k<=i and sum[k] = y (0<=y<=2).

Now, cnt[i+d[i]][s[i]%3] will give me no of k (k<=i+d[i]) such that sum[1…k]%3 = s[i]%3. Similarly for cnt[i][s[i]%3]. So cnt[i+d[i]][s[i]%3] - cnt[i][s[i]%3] will give me no of k (i<k<=i+d[i]) such that sum[1…j]%3 = s[i]%3. However we want no of k (i<k<=i+d[i]) such that the sum[i+1…j] = s[i]%3.
Since cnt[][] consider sum from 1st digit and not from ith digit, I will add sum[1…j] to the condition sum[i+1…j] = s[i]%3 on both sides. So, (sum[1…i] + sum[i+1…j])%3 = (s[i]%3 + sum[1…i])%3. Therefore, sum[1…j] = (s[i]%3 + sum[1…i])%3.
So, we will take t = (sum[i] + s[i])%3. Now, ans[i] = cnt[i+k][t] - cnt[i][t] and if s[i]%3==0, then ++ans[i].

Note : we will not increment cnt[i][y] if s[i]==‘0’ because we dont want the leftmost digit in palindrome to be 0.

My solution : CodeChef: Practical coding for everyone


What is Manachar’s algorithm ?

What is Google?

You can check out manacher’s algorithm here : Manacher's Algorithm | Longest Palindromic Substring - YouTube

" To find ans[i], ans[i] = cnt[i+k][s[i]%3] - cnt[i][s[i]%3] will not work because sum[i] would have contributed to the sum right of I "

Can u pls explain this line once?

I have updated my explanation.

1 Like

Thanks … finally understood :slight_smile:

1 Like