解题思路

要把一个长度为偶数的字符串变为“重复字符串”（前半段与后半段完全相同），最少需要修改多少次？ 设字符串长度为 n，前半段为 s[0..n/2-1]，后半段为 s[n/2..n-1]。要使两半相等，只需逐位比较这两个长度为 n/2 的子串，在每一对对应位置 (i, i+n/2) 上：

• 若字符已相同，则无需修改；
• 若字符不同，则至少需要 1 次修改（把其中任意一个改成另一个即可）。

因此，答案就是两半对应位置的“汉明距离”（不同位置的个数）。 算法：一次线性扫描，统计 s[i] != s[i+n/2] 的次数即可。

复杂度分析

• 时间复杂度：O(n)，只需遍历一遍字符串的一半长度。
• 空间复杂度：O(1)，仅使用常数额外空间。

代码实现

Python

# 计算将字符串变成重复字符串的最小修改次数
def min_ops(s: str) -> int:
    n = len(s)
    half = n // 2
    cnt = 0
    # 逐位比较前半段与后半段
    for i in range(half):
        if s[i] != s[i + half]:
            cnt += 1
    return cnt

if __name__ == "__main__":
    import sys
    # 读取一行字符串
    s = sys.stdin.readline().strip()
    # 输出最小修改次数
    print(min_ops(s))

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    // 外部函数：计算最小修改次数
    static int minOps(String s) {
        int n = s.length();
        int half = n / 2;
        int cnt = 0;
        // 逐位比较前后两半
        for (int i = 0; i < half; i++) {
            if (s.charAt(i) != s.charAt(i + half)) {
                cnt++;
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();      // 读取整行字符串
        if (s == null) s = "";
        s = s.trim();                  // 去除两端空白（题面输入合法，一般为字母）
        System.out.println(minOps(s)); // 输出答案
    }
}

C++

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

// 外部函数：计算最小修改次数
int minOps(const string& s) {
    int n = (int)s.size();
    int half = n / 2;
    int cnt = 0;
    // 逐位比较前半段与后半段
    for (int i = 0; i < half; ++i) {
        if (s[i] != s[i + half]) {
            ++cnt;
        }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if (!getline(cin, s)) s = "";     // 读取整行字符串
    // 输出最小修改次数
    cout << minOps(s) << "\n";
    return 0;
}

题目内容

我们定义一个长度为偶数字符串为重复字符串，当且仅当该字符串的前半段等于后半段。

例如 "$aaaa$"、"$abhabh$" 是重复字符串。

小红拿到了一个字符串，她每次操作可以选择一个字符，将其修改为任意一个字符。

小红想知道，她最少多少次操作后，可以把该字符串变成重复字符串?

输入描述

一个长度为偶数的字符串。长度不超过 $10^5$ 。

输出描述

将其变成重复字符串的最小操作次数。

样例1

输入

abhabh

输出

0

说明

$abhabh$ 本身就是重复字符串，不再需要操作

样例2

输入

abagba

输出

1

说明

将第一个字符改成 '$g$' 即可。