Skip to content

4029. 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 * 104
  • s​​​​​​​​​​​​​​ consists only of lowercase English letters.

Solutions

Solution 1: FFT

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
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;
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
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;
    }
};

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
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)
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
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;
}

Comments