思路：枚举

考虑旋转和修改的关系。

修改完再旋转，很大程度上会将已经修改完的部分变成无用功。

因为修改完，再旋转，会将已经匹配成功的部分会因为一次旋转而不再匹配。

所以我们考虑先旋转，再修改。

即枚举旋转次数，然后考虑修改。

时间复杂度：$O(n^2)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

int op1(const string& s) {
    int res = 0;
    int l = 0;
    int r = s.length() - 1;
    while (l < r) {
        if (s[l] != s[r]) {
            res++;
        }
        l++;
        r--;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = op1(s);

    for (int i = 0; i < n; i++) {
        ans = min(ans, op1(s) + i);
        s = s.substr(1) + s[0];
    }

    cout << ans << "\n";

    return 0;
}

python

def op(s):
    res = 0
    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]:
            res += 1
        l += 1
        r -= 1
    return res


n = int(input())
s = input()
ans = op(s)

for i in range(n):
    ans = min(ans, op(s) + i)
    s = s[1:] + s[0]

print(ans)

Java

import java.util.Scanner;

public class Main {
    public static int op1(String s) {
        int res = 0;
        int l = 0;
        int r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                res++;
            }
            l++;
            r--;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        String s = scanner.next();
        int ans = op1(s);

        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, op1(s) + i);
            s = s.substring(1) + s.charAt(0);
        }

        System.out.println(ans);
    }
}

题目内容

小红有一个长度为$n$的字符串，他想把这个字符串转换为回文串。小红有两种魔法，使用一次魔法需要花费 1 法力值。

第一种魔法可以拿出字符串的第一个字母，并将其插在字符串的末尾。例如，对于字符串 $abbc$ ，通过第一种魔法后后变成了 $bbca$

第二种魔法是将字符串中的一个字符变成任意小写字母。

小红现在问你，需要至少多少法力值才能将这个字符串转换为回文串。

输入描述

第一行，一个正整数$n$，代表字符串的长度

第二行，一个长度为$n$的仅包含小写字母的字符串。

$1 \leq n \leq 10^3$

输出描述

一个整数，表示使得字符串变成回文串的最小法力值。

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

5
kkhbc

输出

2

说明

先试用一次魔法一，字符串变为 $khbck$。

再使用一次魔法二，字符串变为 $kcbck$