文章目录

• 原题
• 具体思路
• 代码

原题

具体思路

1. 首先排除特殊情况，字符串S不能平均分成K份的，
   即S.length()%k ! = 0，都不行，直接返回-1。

2. 满足条件1，但是K=1，不用修改， 直接返回0

3. 上述条件都不满足，

   （1）我们把它分成 K份,用vector数组保存（2）因为我们需要的是尽可能的修改最少的次数，     所以我们就把所有分割出来的字串的相同位置的字符进行比较，     找出出现次数最多的字符，剩下的字符就是我们需要修改的，     即需要修改的=k-maxres（3）不断的重复上面这条，直至子串结束

例如：S=”aabaabcac” ,k=3

代码

#include#include#includeusing namespace std;#includeint 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;}