牛牛喜欢字符串【牛客tracker 每日一题】

牛牛喜欢字符串

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

牛牛现在有一个长度n nn的字符串(仅包含小写字母)，他现在把这个字符串，每隔k kk个就分出来一个子串，比如[ 1 , k ] [1,k][1,k]为第一个子串，[ k + 1 , 2 k ] [k+1,2k][k+1,2k]为第二个、[ 2 k + 1 , 3 k ] [2k+1,3k][2k+1,3k]为第三个…(保证n nn%k = 0 k=0k=0)

牛牛想要把这些子串都变成一样的。他可以选择任意一个子串的任意一个字符进行更改，但是他太懒了，他想让你帮他算算最少要进行多少次操作。

输入描述：

第一行输入n （ 1 ≤ n ≤ 10 6 ） n（1≤n≤10^6）n（1≤n≤106）和k ( 1 ≤ k ≤ n k(1≤k≤nk(1≤k≤n数据保证n nn%k = 0 k=0k=0)，第二行输入该字符串。

输出描述：

输出需要的最少操作次数

示例1

输入：

6 2 abaaba

输出：

2

说明：

改为aaaaaa

示例2

输入：

6 3 abbabb

输出：

0

解题思路

首先明确字符串被等分为n / k n/kn/k个长度为k kk的子串，要让所有子串相同，等价于让所有子串的第j ( 0 ≤ j < k ) j(0≤j<k)j(0≤j<k)个位置的字符一致；解题时遍历每个位置i ii（0 00到k − 1 k-1k−1），统计所有子串中该位置的26 2626个小写字母的出现频次，找出频次最大值m x mxmx，该位置的最少修改次数为子串总数n / k − m x n/k - mxn/k−mx（保留出现最多的字符，其余修改）；累加所有k kk个位置的最少修改次数，得到整体的最少操作次数。该贪心策略保证每个位置的修改数最优，累加后即为全局最优解，字符仅26 2626个，统计频次耗时固定，整体时间复杂度O ( n ) O(n)O(n)，完美适配n ≤ 10 6 n≤10^6n≤106的规模，高效且精准计算出答案。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=2e5+10;intmain(){ll n,k,sum=0;cin>>n>>k;string s;cin>>s;for(ll i=0;i<k;i++){ll cnt[30]={0};for(ll j=i;j<n;j+=k)cnt[s[j]-'a']++;ll mx=0;for(ll i=0;i<26;i++)mx=max(mx,cnt[i]);sum+=n/k-mx;}cout<<sum<<endl;return0;}