小红的项链

[编程题]小红的项链

热度指数：250 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红有一条长度为 $n$ 的项链（ $n$ 保证是偶数），她想把这条项链切成两条长度相等的链（切一对对称的位置），并使得这两条链尽可能相似，小红想知道最大的相似度是多少。

项链：一个环形字符串表示，其中字符串第一个字母和最后一个字母是相邻的。

两条链的相似度：两条链中位置相同且字母相同的位置数量。

注意，切出的两条链按原来的顺序比较相似度，不可以左右翻转。

输入描述:

第一行输入一个长度不超过  的只由小写字母组成的环形字符串。

输出描述:

输出一个整数表示答案。

示例1

输入

cabcdabc

输出

说明

切第1、2个字母之间的位置和第5、6个字母之间的位置，
将项链切成 "abcd" 和 "abcc" ，相似度为3。

算法知识视频讲解

讲道理的打工人面向对象

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
sc.close();

int n = s.length();
int half = n / 2;
String s2 = s + s; // 模拟环形字符串

int similarity = 0;

// 初始窗口的相似度（i = 0）
for (int j = 0; j < half; j++) {
if (s2.charAt(j) == s2.charAt(j + half)) {
similarity++;
}
}

int maxSimilarity = similarity;

// 滑动窗口优化：总共滑动 n - 1 次
for (int i = 1; i < n; i++) {
// 移出旧对（前一个窗口的第一个字符对）
if (s2.charAt(i - 1) == s2.charAt(i - 1 + half)) {
similarity--;
}

// 加入新对（当前窗口的最后一个字符对）
if (s2.charAt(i + half - 1) == s2.charAt(i + n - 1)) {
similarity++;
}

maxSimilarity = Math.max(maxSimilarity, similarity);
}

System.out.println(maxSimilarity);
}
}

发表于 2025-05-17 16:25:33 回复(0)

Python 3