My Approach for Hasan and boring classes :
As the string we have to find must be a palindrome the condition that must hold is T[i] == T[n-1-i] for all i. So for every such pair (i,n-1-i) there are two cases :
Case 1: S[i] == S[n-1-i]
In this case we can either change both the characters to some other character or do not change any of two character. There are 25 ways to change both the characters. There is 1 way to change none of them.
Case 2: S[i] != S[n-1-i]
In this case we can either change the ith character to (n-1-i)th character or change (n-1-i)th character to ith character or change both the characters to some character other than both of them. If we are chnaging only one of them then there are 2 ways and if we are changing both of them there 24 ways.
Some Mathematics before Moving Further
Suppose there are m balls and n bins. Assume bins are distinct. How to put m balls in n bins such that no bins contains more than k balls. There is easy way to deal with such type of problems. Formulate the question in terms of polynomial. So the polynomial for first bin is (x^0 + x^1 + x^2 + … + x^k). x^0 represents we put 0 balls in the bin,and in general x^k represents we put k balls in the bin.And it will be same polynomial for all bins because the max limit is same for all bins. So now our answer will be nothing but just the coefficient of x^m in polynomial generated by multiplication of polynomials of all bins. So answer is coefficient of x^m in (x^0 + x^1 + x^2 + x^3 + … x^k)^n. . Note this logic can even be extended if we have different max limits for each bin.
Solution to original Question
So as discussed above we will create a polynomial for all (i,n-1-i) pairs and then find coefficient of x^k where k is the hamming distance needed. As in our case k is the max hamming distance possible, actual answer is summation that is coeff(x^0) + coeff(x^1) + … + coeff(x^k). Now the polynomial for case 1 is (x^0 + 25*x^2) Here x^0 corresponds to changing 0 characters and x^2 is changing 2 characters and coefficient describes number of ways to do it. Similarly the polynomial for case 2 is (2x^1 + 24x^2).
So now suppose that there are a pairs of case1 and b pairs of case 2 then multiplied polynomial will be (x^0 + 25x^2)^a * (2x^1 + 24*x^2)^b. So now compute first part and second part individually using combinatorial expansion and then use FFT to derive the multiplied polynomial. Now find summation of coeff(x^0) + coeff(x^1) + … + coeff(x^k) in the multiplied polynomial obtained using FFT. That’s the answer.
Note you have to separately handle for the odd case. Because the just middle character, the polynomial will be (x^0 + 25 * x^1). So answer in this case will be ans(S’,k)1 + 25ans(S’,k-1). where S’ is the string obtained by removing the middle character.
Optimization
If we have to find a coefficient of a single power in multiplication of two polynomials A and B, it is just O(N). But here we have to find k such powers. So it is not feasible to do this way and because of this reason only we are using FFT. But wait we have to find summation of coefficients of first k powers then what we can to do just find the coefficient of x^k in the multiplication of (prefix sum polynomial of A) and B. That is define new polynomial A’ where coefficient of x^k is summation of coeff(x^0) + coeff(x^1) + … + coeff(x^k) in polynomial A. Now we have to find just coefficient of x^k in A’B. Remember to expand A upto x^k by appending zeros and then form A’. You can also use B’A instead of A’B because A’B = B’A.
Intuition behind optimization : Suppose I want to buy at most k apples in total from shop A and shop B. Then you can solve this by fixing the amount of apples to buy from shop B and then loop over that fixed amount. That is (0 apple from shop B,at most k apples from shop A), (1 apple from shop B, at most k-1 apples from shop A), … , (k apples from shop B,0 apples from shop A). So for finding coefficient for at-most in A we are using prefix sum polynomial A’.
)
