A40198. 重复字符串
填空题
困难
知识点
题目描述
重复字符串
题目描述
如果一个字符串 SS 恰好可以由某个字符串重复 K 次得到，我们就称 S 是 K 次重复字符串。例如 abcabcabc 可以看作是 abc 重复 3 次得到，所以 abcabcabc 是 3 次重复字符串。
同理 aaaaaa 既是 2 次重复字符串、又是 3 次重复字符串和 6 次重复字符串。
现在给定一个字符串 S，请你计算最少要修改其中几个字符，可以使 S 变为一个 K 次字符串？
输入描述
输入第一行包含一个整数 K。
第二行包含一个只含小写字母的字符串 S。
其中，1 ≤ K ≤ 10^5, 1 ≤ |S| ≤ 10^5。其中 |S| 表示 S 的 长度。
输出描述
输出一个整数代表答案。如果 SS 无法修改成 K 次重复字符串，输出 −1。
样例输入
2
aabbaa
样例输出
2
参考答案
#include<iostream>
#include<string>
#include<vector>
using namespace std;
#include<map>
int solve(string s,int k){
if(s.length()%k!=0) return -1;
if(k==1) return 0;
int num=0,tag=0; //num记录dp数组存放的位置，tag记录每个子串的初始位置
vector<string> dp(k); //取名dp纯属动态规划做多了，习惯
int n=s.length()/k; //每段的长度
while(num<k){
dp[num]=s.substr(tag,n);
tag+=n;
num++;
}
int sum=0; //总的修改次数
for(int i=0;i<n;i++){ //第几个字母
map<char,int> mp; //用map来存放每个字母出现的次数
int res=0;
for(int j=0;j<k;j++){ //第几段子串
mp[dp[j][i]]++;
res=max(res,mp[dp[j][i]]); //每一次都比较，找出出现最多的字母的次数
}
if(res<k) //只有出现的次数小于份数，才需要修改
sum+=k-res;
}
return sum;
}
int main(){
int k;
cin>>k;
string s;
cin>>s;
int res=solve(s,k);
cout<<res<<endl;
}
上一题
下一题