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

HardPremiumFree on FleetCode18 min read

Practice this problem

Problem Statement

You are given a string s consisting of lowercase English letters.

You can perform the following operations any number of times (including zero) and in any order:

Increment: Choose any index i and replace s[i] with the next lowercase English letter. The letter after 'z' is 'a'.
Left rotate: Move the first character of the string to the end.

Return the minimum number of operations required to make s a palindrome.

Example 1:

Input: s = "abc"

Output: 2

Explanation:

One optimal solution:

Left rotate the string: "abc" -> "bca".
Increment 'a' to 'b': "bca" -> "bcb".
"bcb" is a palindrome. Thus, the answer is 2.

Example 2:

Input: s = "yb"

Output: 3

Explanation:

Increment the first character three times: "yb" -> "zb" -> "ab" -> "bb".
"bb" is a palindrome. Thus, the answer is 3.

Constraints:

2 <= s.length <= 5 * 10⁴
s consists only of lowercase English letters.

Approach Overview

Problem Overview: You are given a string and can rotate it any number of times (moving characters from one end to the other). Determine the minimum number of rotations needed so that the resulting string is a palindrome, or return -1 if no rotation works.

Approach 1: Brute Force (O(n²) time, O(n) space)

Generate every rotation by repeatedly moving the first character to the end, then check each rotation for palindromicity using two pointers from both ends. This is straightforward but wasteful: each palindrome check costs O(n) and you try n rotations, giving O(n²). The space is O(n) if you build new strings, or O(1) if you simulate rotations with modular indexing. Use this only as a sanity check for small inputs or as a baseline to verify your optimized solution.

Approach 2: FFT-Based String Matching (O(n log n) time, O(n) space)

This is the optimal approach. The key insight is that checking whether a rotation is a palindrome can be reduced to comparing the original string against its reverse using convolution. Build a combined string S = s + '$' + reverse(s) and compute the convolution of its character-encoded arrays using FFT. For each possible rotation offset k, the convolution result at a specific index tells you how many characters match between s[k:] + s[:k] and its reverse. If that match count equals n, the rotation is a palindrome. Track the minimum k that works. This reduces the problem to a single FFT computation in O(n log n), which is essential for very large inputs (n up to 10^5 or more).

Recommended for interviews: Interviewers expect you to recognize that brute force is too slow and that you need a pattern-matching trick. The FFT approach shows deep understanding of string algorithms and convolution. If you are asked this in an interview, first explain the brute force to show you understand the problem, then pivot to the FFT solution. Mention that rolling hash with binary search on mismatches can also work but is more complex to implement correctly. The FFT solution is clean and demonstrates mastery of advanced techniques.

Solution

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.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force	O(n²)	O(n)	Small inputs or verification
FFT-Based Matching	O(n log n)	O(n)	Large inputs (n > 10^4)

Frequently Asked Questions

Is Minimum Operations to Make a Rotated Palindrome II easy or hard?

It is rated Hard on FleetCode with a 63.6% acceptance rate. The difficulty comes from recognizing that brute force is insufficient and implementing or adapting an FFT-based matching algorithm correctly.

Minimum Operations to Make a Rotated Palindrome II Python/Java solution

In Python, use numpy's FFT or implement a simple FFT with complex numbers. In Java, use a standard iterative FFT implementation or use BigInteger convolution if needed. All solutions are available on FleetCode in Python, Java, C++, Go, and TypeScript.

How to solve Minimum Operations to Make a Rotated Palindrome II in O(n log n)?

Encode the string and its reverse as numeric arrays, concatenate them with a separator, and compute their convolution using FFT. The convolution result at each rotation offset tells how many characters match; if it equals n, that rotation is a palindrome. Track the smallest offset.

What is the best approach for Minimum Operations to Make a Rotated Palindrome II?

The best approach uses FFT-based string matching to compare each rotation against its reverse in O(n log n) time. Brute force checking all rotations costs O(n²), which is too slow for large inputs.

Is Minimum Operations to Make a Rotated Palindrome II asked at Google/Amazon/Meta?

This problem is tagged as Hard and often appears in advanced string algorithm rounds. While not as common as classic problems, its FFT-based solution is relevant for companies that test deep algorithmic knowledge like Google and Meta.

What data structure is used in Minimum Operations to Make a Rotated Palindrome II?

The optimal solution uses arrays for character encoding and relies on Fast Fourier Transform (FFT) for convolution. No complex data structures are needed beyond arrays and complex numbers for the FFT.

What is the time complexity of Minimum Operations to Make a Rotated Palindrome II?

The optimal FFT solution runs in O(n log n) time and uses O(n) space. The brute force approach runs in O(n²) time with O(n) space.

Ready to solve this problem?

Practice Minimum Operations to Make a Rotated Palindrome II with our built-in code editor and test cases.

Practice on FleetCode

Problem Info

DifficultyHard

Acceptance63.7%

Approaches1

Reading time18 min