首页 > 试题广场 >

小红的项链

[编程题]小红的项链

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

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

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

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

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

输出一个整数表示答案。

示例1

输入

cabcdabc

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

算法知识视频讲解

丨阿伟丨

发表于 2025-09-12 18:05:15

题目链接小红的项链题目描述给定一个长度为的环形字符串（是偶数）。我们需要在两个对称的位置切开项链，得到两条长度相等（均为）的链。我们的目标是找到一种切割方式，使得得到的两条链的相似度最大。相似度定义为：两条链在相同位置上拥有相同字符的数量。解题思路这是一个在所有可能的切割方式中寻展开全文

字符串双指针

难度：

2条回答 8收藏 346浏览

小红的项链

扫一扫，把题目装进口袋