小红的回文串

[题目链接](https://www.nowcoder.com/practice/f63e9827b5e349179becdce3bd3be8ca)

思路

本题有两种操作：把首字符移到末尾（旋转）和将任意字符改为任意字母。目标是用最少的总操作次数把字符串变成回文串。

枚举旋转次数

操作一本质上是对字符串做左旋转。旋转 $k$ 次后，原串 $s$ 变为 $s[k], s[k+1], \ldots, s[n-1], s[0], s[1], \ldots, s[k-1]$ 。

对于旋转后的字符串，要将其变成回文串，只需数有多少对位置 $(i, n-1-i)$ 上的字符不同，每对不同只需一次操作二即可修复。

因此，枚举旋转次数 $k$ （从 $0$ 到 $n-1$ ），总操作次数为：

$ $\text{cost}(k) = k + \sum_{i=0}^{\lfloor n/2 \rfloor - 1} [s[(k+i) \bmod n] \neq s[(k+n-1-i) \bmod n]]$ $

答案即为 $\min_{0 \le k < n} \text{cost}(k)$ 。

样例演示

对 $s = \texttt{aacde}$ ：

$k=0$ ：串为 aacde，不匹配对 $(a,e),(a,d)$ ，cost = $0 + 2 = 2$
$k=1$ ：串为 acdea，不匹配对 $(a,a),(c,e)$ ，cost = $1 + 1 = 2$
$k=2$ ：串为 cdeaa，不匹配对 $(c,a),(d,a)$ ，cost = $2 + 2 = 4$
...

最小值为 $2$ ，与预期一致。

复杂度分析

时间复杂度： $O(n^2)$ ，外层枚举 $n$ 种旋转，内层检查 $n/2$ 对字符。
空间复杂度： $O(n)$ ，只需存储输入字符串。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = n;
    for(int k = 0; k < n; k++){
        int changes = 0;
        for(int i = 0; i < n/2; i++){
            int li = (k + i) % n;
            int ri = (k + n - 1 - i) % n;
            if(s[li] != s[ri]) changes++;
        }
        ans = min(ans, k + changes);
    }
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        int ans = n;
        for (int k = 0; k < n; k++) {
            int changes = 0;
            for (int i = 0; i < n / 2; i++) {
                int li = (k + i) % n;
                int ri = (k + n - 1 - i) % n;
                if (s.charAt(li) != s.charAt(ri)) changes++;
            }
            ans = Math.min(ans, k + changes);
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline
n = int(input())
s = input().strip()
ans = n
for k in range(n):
    changes = 0
    for i in range(n // 2):
        li = (k + i) % n
        ri = (k + n - 1 - i) % n
        if s[li] != s[ri]:
            changes += 1
    ans = min(ans, k + changes)
print(ans)

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