Minimum Operations to Make a Rotated Palindrome II - Solution & Explanation

This problem is the same as "Minimum Operations to Make a Rotated Palindrome I", but n can be as large as 5 times 10^4, so enumerating rotations and pairing characters naively is too slow.

After k left rotations, index i in the new string corresponds to index (i+k) bmod n in the original string. The sum of original indices of a palindrome pair (i, n-1-i) is 2k+n-1, which is constant for all pairs. Thus, after k rotations, every pair has original-index sum congruent to c = (2k+n-1) bmod n.

The increment cost of two letters is the shorter arc min(d, 26-d) on the letter ring. Viewing the cost as a function on \mathbb{Z}/26\mathbb{Z} and expanding it by the discrete Fourier transform, we map each character x to the phase e^{2\pi i t x / 26} for each frequency t, then compute a circular convolution of the sequence. This yields the total pairing cost for every index-sum c at once. Since the cost function is even, we only need frequencies t = 0, ldots, 13 (the rest follow by conjugate symmetry). Each pair is counted twice, and we also divide by 26 from the DFT, so dividing the convolution by 52 and rounding gives the increment cost.

For each k, the candidate answer is k plus the increment cost of the corresponding c. We take the minimum.

The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the string.