4021. Minimum Operations to Make a Rotated Palindrome I

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 <= 2000
s consists only of lowercase English letters.

Solutions

Solution 1: Enumeration

Thinking

There are only \(n\le 2000\) left rotations, and pairing characters after each rotation is \(O(n^2)\), which fits the limit.

Letters may only increment around the alphabet, so the cheapest way to equalise a pair is the shorter arc \(\min(d,26-d)\); the optimal target is one of the two letters.

Adding the rotation cost \(k\) to every pair's increment cost and taking the minimum yields the answer.

We enumerate the number of left rotations \(k\) (\(0 \leq k < n\)), which costs \(k\) operations. After \(k\) left rotations, index \(i\) in the new string corresponds to index \((i + k) \bmod n\) in the original string.

For each pair of symmetric positions, we need to make the two characters the same by increment operations. Since we can only increment forward ('z' wraps to 'a'), the minimum number of increments to make two letters equal is the shorter arc length on the letter ring, i.e., \(\min(d, 26 - d)\), where \(d\) is the absolute difference of their letter indices. The optimal target letter is always one of the two letters.

We take the minimum over all \(k\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(1)\), where \(n\) is the length of the string.

Python3JavaC++GoTypeScript

class Solution:
    def minOperations(self, s: str) -> int:
        n = len(s)
        ans = inf
        for k in range(n):
            t = k
            i, j = 0, n - 1
            while i < j:
                x = ord(s[(i + k) % n]) - ord('a')
                y = ord(s[(j + k) % n]) - ord('a')
                d = abs(x - y)
                t += min(d, 26 - d)
                i, j = i + 1, j - 1
            ans = min(ans, t)
        return ans

class Solution {
    public int minOperations(String s) {
        int n = s.length();
        int ans = Integer.MAX_VALUE;

        for (int k = 0; k < n; k++) {
            int t = k;
            int i = 0, j = n - 1;

            while (i < j) {
                int x = s.charAt((i + k) % n) - 'a';
                int y = s.charAt((j + k) % n) - 'a';

                int d = Math.abs(x - y);
                t += Math.min(d, 26 - d);

                i++;
                j--;
            }

            ans = Math.min(ans, t);
        }

        return ans;
    }
}

class Solution {
public:
    int minOperations(string s) {
        int n = s.size();
        int ans = INT_MAX;

        for (int k = 0; k < n; ++k) {
            int t = k;
            int i = 0, j = n - 1;

            while (i < j) {
                int x = s[(i + k) % n] - 'a';
                int y = s[(j + k) % n] - 'a';

                int d = abs(x - y);
                t += min(d, 26 - d);

                ++i;
                --j;
            }

            ans = min(ans, t);
        }

        return ans;
    }
};

func minOperations(s string) int {
    n := len(s)
    ans := int(^uint(0) >> 1)

    for k := 0; k < n; k++ {
        t := k
        i, j := 0, n-1

        for i < j {
            x := int(s[(i+k)%n] - 'a')
            y := int(s[(j+k)%n] - 'a')

            d := abs(x - y)
            t += min(d, 26-d)

            i++
            j--
        }

        ans = min(ans, t)
    }

    return ans
}

func abs(x int) int {
    return max(x, -x)
}

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

    for (let k = 0; k < n; k++) {
        let t = k;
        let i = 0;
        let j = n - 1;

        while (i < j) {
            const x = s.charCodeAt((i + k) % n) - 97;
            const y = s.charCodeAt((j + k) % n) - 97;

            const d = Math.abs(x - y);
            t += Math.min(d, 26 - d);

            i++;
            j--;
        }

        ans = Math.min(ans, t);
    }

    return ans;
}

4021. Minimum Operations to Make a Rotated Palindrome I

Description

Solutions

Solution 1: Enumeration

Comments