For the sake of simplicity, let's assume that we are only dealing with palindromes of odd length, and that the described solution is easily expanded to the general case. The center of a palindrome is the character in its middle, or the position of that character in the original sample. The first step of the solution is, for each position ~a~ ~(1 \le a \le n)~, to determine ~r_a~ – the half length of the longest palindrome with its center at ~a~ (the longest palindrome with its center in ~a~ is ~w_{a-r_a,a+r_a}~). Notice that the weight of the original sample is equal to the sum of all the numbers ~r_a+1~.

There are multiple efficient ways to calculate all numbers ~r_a~. One option is, for each position ~a~, to determine the value ~r_a~ with binary search. In order for this approach to be efficient enough, we need to have a method that can quickly examine whether two arbitrary substrings of sample ~w~, for example ~w_{x,y}~ and ~w_{u,v}~, are equal. This can be done using the so-called rolling hash function. (Curator's note: This website is in Croatian. Thanks, COCI.)

When we have calculated all the values ~r_a~, we know the current weight of the sample. In the second step of the solution, we examine how the weight changes if the character at position ~i~ is converted to ~c~. After conversion, some palindromes disappear, and new ones appear. First, we calculate how many existing palindromes disappear.

Let's now consider only palindromes with its center at ~a~. Some of them disappear only if the converted character's position is from the interval ~[a-r_a, a+r_a]~, and if, for example, the position of conversion ~i~ is from the interval ~[a-r_a, a]~, then exactly ~i-(a-r_a)+1~ palindromes with centers in ~a~ disappear. With the help of this fact, we can implement a sweep line algorithm that calculates in a single pass, for each position, the total number of palindromes that disappear if the character is converted at that position.

We still need to find the number of newly created palindromes for each possible conversion. Let's assume that, after the conversion at position ~i~ into character ~c~, a new palindrome appears with its center in ~a~, where ~i < a~. Let ~d = a-i~. Therefore, the sample ~w_{a-d,a+d}~ was not a palindrome before conversion, and now is. Since ~w_{a-d,a+d}~ is now a palindrome, so is ~w_{a-d+1,a+d-1}~, but this sample hasn't been changed, so it was a palindrome before conversion. Hence, ~w_{a-d+1,a+d-1}~ was the longest palindrome with its center in ~a~ before conversion, so ~d~ is equal to ~r_a+1~. We conclude that each new palindrome with its center in ~a~ can appear so that either the character at position ~a-r_a-1~ is converted to the character at position ~a+r_a+1~ or vice versa. Therefore, similarly to how we calculated ~r_a~ (binary search with hash function to compare strings), we can calculate the number of new palindromes that appear in each of the two cases. Now we have calculated everything we need in order to know how many palindromes appear for each position ~i~ and each new character ~c~, and how many disappear if the character at position ~i~ is converted to ~c~, so the task is solved.