小红的字符串

思路

拿到这道题，先想想回文串的性质：一个回文串满足 s[i] == s[n-1-i]，也就是首尾对称的字符必须相同。

那操作是什么呢？每次可以把一个字符循环右移到字母表的下一个字母（'a'->'b'->'c'->...->'z'->'a'）。问最少操作多少次能把字符串变成回文串。

怎么拆解这个问题？

既然回文串要求对称位置的字符相等，我们只需要关注每一对 (s[i], s[n-1-i]) 就行了。每一对是独立的——把这对变成相同字符的最小代价加起来，就是总答案。

那对于一对字符 (a, b)，怎么用最少的右移操作让它们相等？

我们可以只移 a，也可以只移 b，还可以两个都移，让它们在某个中间字符碰头。比如 a 右移 x 步，b 右移 y 步，需要 (a + x) % 26 == (b + y) % 26，代价是 x + y。

仔细想一下：字母表是一个长度为 26 的环。两个字符在环上的距离有两个方向——顺时针走 d 步，或者逆时针走 26 - d 步。不管走哪个方向，我们都可以只移一边就搞定（让靠后的那个不动，靠前的追上去）。所以最优策略就是取两个方向中较短的那个。

具体做法

  1. 遍历前半段 i = 0, 1, ..., n/2 - 1
  2. 对每对 (s[i], s[n-1-i])，算出顺时针距离 d = (s[n-1-i] - s[i] + 26) % 26
  3. 这一对的代价是 min(d, 26 - d)
  4. 累加所有对的代价就是答案

如果字符串长度是奇数，中间那个字符不用管，它自己就是对称的。

代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    long long ans = 0;
    for (int i = 0; i < n / 2; i++) {
        int d = (s[n - 1 - i] - s[i] + 26) % 26;
        ans += min(d, 26 - d);
    }
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();
        long ans = 0;
        for (int i = 0; i < n / 2; i++) {
            int d = (s.charAt(n - 1 - i) - s.charAt(i) + 26) % 26;
            ans += Math.min(d, 26 - d);
        }
        System.out.println(ans);
    }
}

s = input()
n = len(s)
ans = 0
for i in range(n // 2):
    d = (ord(s[n - 1 - i]) - ord(s[i]) + 26) % 26
    ans += min(d, 26 - d)
print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const s = lines[0].trim();
    const n = s.length;
    let ans = 0;
    for (let i = 0; i < Math.floor(n / 2); i++) {
        const d = (s.charCodeAt(n - 1 - i) - s.charCodeAt(i) + 26) % 26;
        ans += Math.min(d, 26 - d);
    }
    console.log(ans);
});

复杂度分析

  • 时间复杂度: ，只遍历半个字符串
  • 空间复杂度: ，存储输入字符串

总结

这道题的核心是把"整个字符串变回文"拆成"每一对对称位置的字符变相同"，然后在字母表这个环上找最短距离。想通了环上两点最短距离取 min(d, 26-d) 这一步，代码写出来就几行的事。贪心的思想在于：每一对独立处理，局部最优即全局最优。