PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Let s be the given string, n is its length and s[i] denotes i-th symbol of s (0 <= i < n). Also we denote by s[i, j)** the substring of s from **i**-th symbol inclusive to j-th symbol not inclusive. Compute for each i the so-called palindrome radius **d[i]. Namely d[i] is the maximal number k such that the substring s[i - k, i + k)** is a palindrome. This can be done by the elegant Manacher algorithm in **O(n)** time. Here you can read about it. Also you can use hashes and binary search to find this in **O(n log n)** time. So now assume that we find numbers **d[i] (0 <= i < n). Obviously the substring s[i - k, i+3 * k)** is beautiful if and only if **j <= i + d[i] and d[j] >= 2 * (j - i) where j = i + k. (Since j <= i + d[i] then substring s[i - k, i + k)** is a palindrome and since **d[j] >= 2 * k then s[i - k, i+3 * k)** is also a palindrome and has the form **tt<sup>r</sup>tt<sup>r</sup>** where **t** = **s[i - k, i)**). So for each i the number of beautiful substrings of the form **s[i - k, i+3 * k)** is equal to number of those **j <= i + d[i] such that 2 * j - d[j] <= 2 * i (and of course j > i). Let’s sort all pairs (2 * j - d[j], j) by the usual lexicographical comparator. For each i from 0 to n-1 we at first add all new values of j such that 2 * j - d[j] <= 2 * i to some data structure T then delete i from T and then add to the answer the number of elements in T that are not greater than i + d[i]. Obviously when we are finding the last quantity, T contains only those values of j such that i < j (since we delete i at each step) and 2 * j - d[j] <= 2 * i. So the last quantity is number of beautiful substring of the form s[i - k, i+3 * k). What is T? We can use Cartesian tree or any balanced binary search tree that support order statistics as T. Also we can use segment tree for sum on the array of numbers from 0 to n-1. Then insertion (deleting) of the element is simply adding (subtraction) of one to (from) the corresponding element of the array and the number of needed beautiful substrings is the sum of values of the corresponding segment of the array. Finally you can use Fenwick tree instead of the segment tree (see author solution). So the overall complexity is O(n log n).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.