4028. Minimum Operations to Make a Rotated Palindrome II 🔒

Description

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.

Solutions

Solution 1: FFT

Thinking

The pairing model is the same as in the rotated-palindrome I problem, but $n$ reaches $5\times 10^4$, so enumerating $k$ and scanning pairs is no longer feasible.

After $k$ left rotations, every palindromic pair has original indices summing to the same $c=(2k+n-1)\bmod n$ modulo $n$. The remaining work is the total shorter-arc cost for every index-sum $c$.

That cost is an even function on $\mathbb{Z}/26\mathbb{Z}$. Its DFT followed by a circular convolution yields every $c$ at once; we add the rotation count $k$ and take the minimum. Conjugate symmetry leaves only $14$ frequencies.

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.

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;
    }
}

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;
    }
};

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

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)
}

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;
}

4028 - Minimum Operations to Make a Rotated Palindrome II

4028. Minimum Operations to Make a Rotated Palindrome II 🔒

Description

Solutions

Solution 1: FFT

All Problems

All Solutions

Welcome to Subscribe On Youtube

4028. Minimum Operations to Make a Rotated Palindrome II 🔒

Description

Solutions

Solution 1: FFT

All Problems

All Solutions