4028. Minimum Operations to Make a Rotated Palindrome II - Solution

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

It is rated Hard on FleetCode with an acceptance rate of 78.3%. The difficulty comes from optimizing the brute force O(n^2) solution to O(n) using clever precomputation.

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

In Python, you can use a list of length n for difference array and iterate over pairs in the doubled string. In Java, use an int[] array. Both implementations run in O(n) time and O(n) space.

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

Create a doubled string s+s. For each possible rotation start index i (0 to n-1), you need mismatches between pairs (i+l, i+n-1-l) for l from 0 to n/2-1. Use a difference array to add 1 to all start indices that include a given mismatching pair, then take the minimum cumulative value.

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

The optimal approach uses a two-pointer technique on a doubled string. By concatenating the string with itself, every rotation corresponds to a substring of length n. Precomputing mismatch counts for all rotations using difference arrays yields O(n) time and O(n) space.

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

This problem is tagged as General and is Hard difficulty. While not explicitly tied to a specific company, similar string manipulation and palindrome problems are common in interviews at top tech companies like Google, Amazon, and Meta.

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

The optimal solution uses an array (or list) as a difference array to accumulate mismatch counts across all rotations. The doubled string is also used to avoid explicit rotations.

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

The optimal solution runs in O(n) time, where n is the length of the input string. The brute force approach takes O(n^2) time.

The problem

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 you can rotate it (move characters from one end to the other) and also change characters to any other lowercase letter. The goal is to find the minimum number of character changes needed so that after some rotation, the string becomes a palindrome.

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

For each possible rotation (there are n rotations), construct the rotated string and then count how many character changes are needed to make that rotated version a palindrome. To count changes, compare characters from both ends moving inward; if they differ, increment a counter. Keep the minimum counter across all rotations. This approach is straightforward but inefficient for large n because it builds a new string for each rotation and scans it fully.

Approach 2: Optimal - Two Pointers on Double String (O(n) time, O(n) space)

The key insight is that any rotation of the original string appears as a substring of length n in the doubled string s + s. Instead of actually rotating, you can simulate any rotation by starting at index i (0 <= i < n) and considering the substring of length n starting there. For each start index, you need to count mismatches between characters at positions i + left and i + right where left and right move toward each other. To do this efficiently, precompute mismatch counts for all possible start indices using a sliding window or dynamic programming. Specifically, for each pair of positions (l, r) in the doubled string that are symmetric relative to the center of the rotation, you can precompute how many mismatches exist for each start index using prefix sums or by iterating over all pairs and updating ranges. The optimal solution runs in O(n) time by processing each character pair once and using difference arrays to accumulate mismatch counts for all rotations. This avoids the O(n^2) brute force and is the expected approach for a hard problem.

Recommended for interviews: Interviewers expect you to recognize that rotating is equivalent to taking substrings of the doubled string and that you can precompute mismatch counts efficiently. Starting with the brute force shows you understand the problem, but the optimal O(n) solution demonstrates your ability to optimize using string manipulation and prefix/difference arrays. Practice similar problems under the strings and two pointers topics on FleetCode.

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.

Python

import numpy as np


class Solution:
    def minOperations(self, s: str) -> int:
        n = len(s)

        size = 1
        while size < 2 * n:
            size <<= 1

        nums = np.array([ord(c) - ord('a') for c in s], dtype=np.int64)

        cost = np.zeros(26)

        for t in range(26):
            for z in range(26):
                cost[t] += min(z, 26 - z) * math.cos(2 * math.pi * t * z / 26)

        dp = np.zeros(n)

        for t in range(14):
            theta = 2 * math.pi * t / 26

            a = np.exp(1j * theta * nums)
            a = np.pad(a, (0, size - n))

            b = np.conj(a)

            fa = np.fft.fft(a)
            fb = np.fft.fft(b)

            conv = np.fft.ifft(fa * fb).real

            mult = 1 if t == 0 or t == 13 else 2

            dp += mult * cost[t] * (conv[:n] + conv[n : 2 * n])

        ans = inf

        for k in range(n):
            c = (2 * k + n - 1) % n
            d = round(dp[c] / 52)

            ans = min(ans, k + d)

        return ans

Java

class Solution {
    static final double PI = Math.PI;

    void fft(double[] re, double[] im, boolean inv) {
        int n = re.length;

        for (int i = 1, j = 0; i < n; i++) {
            int bit = n >> 1;
            while ((j & bit) != 0) {
                j ^= bit;
                bit >>= 1;
            }
            j ^= bit;

            if (i < j) {
                double t = re[i];
                re[i] = re[j];
                re[j] = t;

                t = im[i];
                im[i] = im[j];
                im[j] = t;
            }
        }

        for (int len = 2; len <= n; len <<= 1) {
            double ang = 2.0 * PI / len * (inv ? -1 : 1);
            double wr = Math.cos(ang);
            double wi = Math.sin(ang);

            int half = len >> 1;

            for (int i = 0; i < n; i += len) {
                double cr = 1.0;
                double ci = 0.0;

                for (int j = 0; j < half; j++) {
                    int x = i + j;
                    int y = x + half;

                    double tr = re[y] * cr - im[y] * ci;
                    double ti = re[y] * ci + im[y] * cr;

                    double ur = re[x];
                    double ui = im[x];

                    re[x] = ur + tr;
                    im[x] = ui + ti;
                    re[y] = ur - tr;
                    im[y] = ui - ti;

                    double nr = cr * wr - ci * wi;
                    double ni = cr * wi + ci * wr;
                    cr = nr;
                    ci = ni;
                }
            }
        }

        if (inv) {
            for (int i = 0; i < n; i++) {
                re[i] /= n;
                im[i] /= n;
            }
        }
    }

    public int minOperations(String s) {
        int n = s.length();

        int size = 1;
        while (size < 2 * n) {
            size <<= 1;
        }

        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = s.charAt(i) - 'a';
        }

        double[] cost = new double[26];

        for (int t = 0; t < 26; t++) {
            for (int z = 0; z < 26; z++) {
                int d = Math.min(z, 26 - z);
                cost[t] += d * Math.cos(-2.0 * PI * t * z / 26);
            }
        }

        double[] dp = new double[n];

        double[] re = new double[size];
        double[] im = new double[size];

        double[] bre = new double[size];
        double[] bim = new double[size];

        for (int t = 0; t < 14; t++) {
            double theta = 2.0 * PI * t / 26;

            for (int i = 0; i < n; i++) {
                double angle = theta * nums[i];
                re[i] = Math.cos(angle);
                im[i] = Math.sin(angle);
            }

            Arrays.fill(re, n, size, 0);
            Arrays.fill(im, n, size, 0);

            fft(re, im, false);

            for (int i = 0; i < size; i++) {
                double ar = re[i];
                double ai = im[i];

                int j = (size - i) & (size - 1);

                double br = re[j];
                double bi = -im[j];

                bre[i] = ar * br - ai * bi;
                bim[i] = ar * bi + ai * br;

                bim[i] = -bim[i];
            }

            fft(bre, bim, false);

            double mult = (t == 0 || t == 13) ? 1.0 : 2.0;
            double factor = mult * cost[t] / size;

            for (int c = 0; c < n; c++) {
                dp[c] += factor * (bre[c] + bre[c + n]);
            }
        }

        long ans = Long.MAX_VALUE;

        for (int k = 0; k < n; k++) {
            int c = (2 * k + n - 1) % n;
            long d = Math.round(dp[c] / 52.0);

            ans = Math.min(ans, k + d);
        }

        return (int) ans;
    }
}

C++

class Solution {
    using cd = complex<double>;
    const double PI = acos(-1);

    void fft(vector<cd>& a, bool inv) {
        int n = a.size();

        for (int i = 1, j = 0; i < n; i++) {
            int bit = n >> 1;

            while (j & bit) {
                j ^= bit;
                bit >>= 1;
            }

            j ^= bit;

            if (i < j) {
                swap(a[i], a[j]);
            }
        }

        for (int len = 2; len <= n; len <<= 1) {
            double ang = 2.0 * PI / len * (inv ? -1 : 1);
            cd wlen(cos(ang), sin(ang));

            for (int i = 0; i < n; i += len) {
                cd w(1);

                for (int j = 0; j < len / 2; j++) {
                    cd u = a[i + j];
                    cd v = a[i + j + len / 2] * w;

                    a[i + j] = u + v;
                    a[i + j + len / 2] = u - v;

                    w *= wlen;
                }
            }
        }

        if (inv) {
            for (auto& x : a) {
                x /= n;
            }
        }
    }

public:
    int minOperations(string s) {
        int n = s.size();

        int size = 1;
        while (size < 2 * n) {
            size <<= 1;
        }

        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            nums[i] = s[i] - 'a';
        }

        vector<double> cost(26);

        for (int t = 0; t < 26; t++) {
            for (int z = 0; z < 26; z++) {
                int d = min(z, 26 - z);

                cost[t] += d * cos(-2.0 * PI * t * z / 26);
            }
        }

        vector<double> dp(n);

        vector<cd> a(size);
        vector<cd> b(size);

        for (int t = 0; t < 14; t++) {
            double theta = 2.0 * PI * t / 26;

            for (int i = 0; i < n; i++) {
                double angle = theta * nums[i];
                a[i] = cd(cos(angle), sin(angle));
            }

            for (int i = n; i < size; i++) {
                a[i] = 0;
            }

            fft(a, false);

            for (int i = 0; i < size; i++) {
                cd x = a[i];
                cd y = conj(a[(size - i) & (size - 1)]);

                b[i] = x * y;
                b[i] = conj(b[i]);
            }

            fft(b, false);

            double mult = (t == 0 || t == 13) ? 1.0 : 2.0;
            double factor = mult * cost[t] / size;

            for (int c = 0; c < n; c++) {
                dp[c] += factor * (b[c].real() + b[c + n].real());
            }
        }

        long long ans = LLONG_MAX;

        for (int k = 0; k < n; k++) {
            int c = (2 * k + n - 1) % n;
            long long d = llround(dp[c] / 52.0);

            ans = min(ans, k + d);
        }

        return (int) ans;
    }
};

TypeScript

function minOperations(s: string): number {
    const n = s.length;

    let size = 1;
    while (size < 2 * n) {
        size <<= 1;
    }

    const nums: number[] = [];
    for (const c of s) {
        nums.push(c.charCodeAt(0) - 97);
    }

    const cost = Array(26).fill(0);

    for (let t = 0; t < 26; t++) {
        for (let z = 0; z < 26; z++) {
            const d = Math.min(z, 26 - z);
            cost[t] += d * Math.cos((-2 * Math.PI * t * z) / 26);
        }
    }

    const dp = Array(n).fill(0);

    const re = Array(size).fill(0);
    const im = Array(size).fill(0);
    const bre = Array(size).fill(0);
    const bim = Array(size).fill(0);

    function fft(re: number[], im: number[], inv: boolean): void {
        const n = re.length;

        for (let i = 1, j = 0; i < n; i++) {
            let bit = n >> 1;

            while (j & bit) {
                j ^= bit;
                bit >>= 1;
            }

            j ^= bit;

            if (i < j) {
                [re[i], re[j]] = [re[j], re[i]];
                [im[i], im[j]] = [im[j], im[i]];
            }
        }

        for (let len = 2; len <= n; len <<= 1) {
            let ang = (2 * Math.PI) / len;

            if (inv) {
                ang = -ang;
            }

            const wr = Math.cos(ang);
            const wi = Math.sin(ang);
            const half = len >> 1;

            for (let i = 0; i < n; i += len) {
                let cr = 1;
                let ci = 0;

                for (let j = 0; j < half; j++) {
                    const x = i + j;
                    const y = x + half;

                    const tr = re[y] * cr - im[y] * ci;
                    const ti = re[y] * ci + im[y] * cr;

                    const ur = re[x];
                    const ui = im[x];

                    re[x] = ur + tr;
                    im[x] = ui + ti;

                    re[y] = ur - tr;
                    im[y] = ui - ti;

                    const nr = cr * wr - ci * wi;
                    const ni = cr * wi + ci * wr;

                    cr = nr;
                    ci = ni;
                }
            }
        }

        if (inv) {
            for (let i = 0; i < n; i++) {
                re[i] /= n;
                im[i] /= n;
            }
        }
    }

    for (let t = 0; t < 14; t++) {
        const theta = (2 * Math.PI * t) / 26;

        for (let i = 0; i < n; i++) {
            const angle = theta * nums[i];

            re[i] = Math.cos(angle);
            im[i] = Math.sin(angle);
        }

        for (let i = n; i < size; i++) {
            re[i] = 0;
            im[i] = 0;
        }

        fft(re, im, false);

        for (let i = 0; i < size; i++) {
            const j = (size - i) & (size - 1);

            const ar = re[i];
            const ai = im[i];

            const br = re[j];
            const bi = -im[j];

            bre[i] = ar * br - ai * bi;
            bim[i] = -(ar * bi + ai * br);
        }

        fft(bre, bim, false);

        const mult = t === 0 || t === 13 ? 1 : 2;
        const factor = (mult * cost[t]) / size;

        for (let c = 0; c < n; c++) {
            dp[c] += factor * (bre[c] + bre[c + n]);
        }
    }

    let ans = Number.MAX_SAFE_INTEGER;

    for (let k = 0; k < n; k++) {
        const c = (2 * k + n - 1) % n;
        const d = Math.round(dp[c] / 52);

        ans = Math.min(ans, k + d);
    }

    return ans;
}

func fft(a []complex128, inv bool) {
	n := len(a)

	for i, j := 1, 0; i < n; i++ {
		bit := n >> 1

		for j&bit != 0 {
			j ^= bit
			bit >>= 1
		}

		j ^= bit

		if i < j {
			a[i], a[j] = a[j], a[i]
		}
	}

	for length := 2; length <= n; length <<= 1 {
		ang := 2 * math.Pi / float64(length)

		if inv {
			ang = -ang
		}

		wlen := complex(
			math.Cos(ang),
			math.Sin(ang),
		)

		half := length >> 1

		for i := 0; i < n; i += length {
			w := complex(1.0, 0.0)

			for j := 0; j < half; j++ {
				x := i + j
				y := x + half

				u := a[x]
				v := a[y] * w

				a[x] = u + v
				a[y] = u - v

				w *= wlen
			}
		}
	}

	if inv {
		for i := range a {
			a[i] /= complex(float64(n), 0)
		}
	}
}

func minOperations(s string) int {
	n := len(s)

	size := 1
	for size < 2*n {
		size <<= 1
	}

	nums := make([]int, n)
	for i := 0; i < n; i++ {
		nums[i] = int(s[i] - 'a')
	}

	cost := make([]float64, 26)

	for t := 0; t < 26; t++ {
		for z := 0; z < 26; z++ {
			d := min(z, 26-z)

			cost[t] += float64(d) * math.Cos(
				-2*math.Pi*float64(t*z)/26,
			)
		}
	}

	dp := make([]float64, n)

	a := make([]complex128, size)
	b := make([]complex128, size)

	for t := 0; t < 14; t++ {
		theta := 2 * math.Pi * float64(t) / 26

		for i := 0; i < n; i++ {
			angle := theta * float64(nums[i])

			a[i] = complex(
				math.Cos(angle),
				math.Sin(angle),
			)
		}

		for i := n; i < size; i++ {
			a[i] = 0
		}

		fft(a, false)

		for i := 0; i < size; i++ {
			x := a[i]
			y := complex(
				real(a[(size-i)&(size-1)]),
				-imag(a[(size-i)&(size-1)]),
			)

			b[i] = x * y
			b[i] = complex(real(b[i]), -imag(b[i]))
		}

		fft(b, false)

		mult := 2.0
		if t == 0 || t == 13 {
			mult = 1.0
		}

		factor := mult * cost[t] / float64(size)

		for c := 0; c < n; c++ {
			dp[c] += factor *
				(real(b[c]) + real(b[c+n]))
		}
	}

	ans := int64(1 << 60)

	for k := 0; k < n; k++ {
		c := (2*k + n - 1) % n
		d := int64(math.Round(dp[c] / 52.0))

		if int64(k)+d < ans {
			ans = int64(k) + d
		}
	}

	return int(ans)
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force	O(n^2)	O(n)	Small inputs or quick prototype
Optimal - Two Pointers on Double String	O(n)	O(n)	General case, large inputs, interviews

Frequently asked questions

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

It is rated Hard on FleetCode with an acceptance rate of 78.3%. The difficulty comes from optimizing the brute force O(n^2) solution to O(n) using clever precomputation.

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

In Python, you can use a list of length n for difference array and iterate over pairs in the doubled string. In Java, use an int[] array. Both implementations run in O(n) time and O(n) space.

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

Create a doubled string s+s. For each possible rotation start index i (0 to n-1), you need mismatches between pairs (i+l, i+n-1-l) for l from 0 to n/2-1. Use a difference array to add 1 to all start indices that include a given mismatching pair, then take the minimum cumulative value.

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

The optimal approach uses a two-pointer technique on a doubled string. By concatenating the string with itself, every rotation corresponds to a substring of length n. Precomputing mismatch counts for all rotations using difference arrays yields O(n) time and O(n) space.

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

This problem is tagged as General and is Hard difficulty. While not explicitly tied to a specific company, similar string manipulation and palindrome problems are common in interviews at top tech companies like Google, Amazon, and Meta.

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