### PROBLEM LINK:

**Author:** Konstantin Sokol

**Tester:** Gerald Agapov

**Editorialist:** Tasnim Imran Sunny

### DIFFICULTY:

Medium

### PREREQUISITES:

Manacher’s Algorithm

### PROBLEM:

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.

### EXPLANATION:

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) = **S _{i} + S_{i+1} + … + S_{j}**

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, **S _{i-k} … S_{i} … S_{i+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:

**( S _{i} + 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 **S _{i} != 0** are considered in the precomputation.

The even length palindromes can be counted similarly.

The complexity of the solution is **O(N)**.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.