首页 > 试题广场 >

小红的双生串

[编程题]小红的双生串
  • 热度指数：3995 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小红定义一个字符串是双生串，当且仅当其前半部分所有字符相同，后半部分所有字符相同。
\hspace{15pt}现在，小红拿到了一个字符串 s ，她每次操作可以修改一个字符。小红希望你求出将其修改为双生串的最小修改次数。

输入描述:
\hspace{15pt}在一行上输入一个长度为 1 \leqq {\rm len}(s) \leqq 2 \times 10^5 且为偶数，仅由小写字母构成的字符串 s，代表待修改的字符串。


输出描述:
\hspace{15pt}输出一个整数，表示将 s 修改为双生串的最小修改次数。
示例1

输入

popipa

输出

3

说明

\hspace{15pt}在这个样例中，将 s 修改为 \texttt{ 是其中一个最优解。
示例2

输入

aaaa

输出

0

说明

\hspace{15pt}在这个样例中，给定的字符串已经是双生串，不需要修改。
算法知识视频讲解
添加回答
C
在考古的coder很讲原则头像 在考古的coder很讲原则
#include <stdio.h>
#include <string.h>
int main()
{
    char s[200001];
    int hash1[128]={0},hash2[128]={0};
    scanf("%s",s);
    int m=strlen(s),max1=0,max2=0,tmp;
    for(int i=0;i<m/2;i++)
    {
        int asc=(int)s[i];
        hash1[asc]++;
    }
    for(int i=0;i<128;i++)
    {
        if(hash1[i]>max1)
        max1=hash1[i];
    }
    for(int i=m-1;i>=m/2;i--)
    {
        int asc=(int)s[i];
        hash2[asc]++;
    }
    for(int i=0;i<128;i++)
    {
        if(hash2[i]>max2)
        max2=hash2[i];
    }
    printf("%d",m-max1-max2);
}
发表于 2025-03-19 10:50:16 回复(0)
提交观点

问题信息

动态规划
难度：
1条回答 524浏览

热门推荐

相关试题

小红的双生串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号