[题解] String I

出题人题解：https://blog.nowcoder.net/n/c47b98907d8147e39a58175c4489374e

出题人的题解中最优复杂度为 ，事实上这道题可以用尺取优化到 的复杂度。这样数据出到 的字符串长度也是可以通过的。（这样难度可以由3提高到4）
考查知识点：中位数/枚举、桶计数、尺取
思路：每次操作可以将一个字母加一或者减一，那么显然，要把区间所有字母变为相等，最小操作次数只需要把所有字母变成区间的“中位数”即可。由于一共只有 个字母，因此可以用一个桶来计数，计算区间是否合法的复杂度仅为 （如果用 ，复杂度为 且常数较大，不推荐）。或者直接枚举所有变化情况求出最小值也是可以的（同样利用桶计数），不过这样复杂度将变成 。然后用双指针尺取，维护合法区间长度的最大值即可。
总复杂度：

参考代码：

int string1(int k, string s) {
        // write code here
        int i,x,j=0,ma=0;
        int t[26]={0};
        for(i=0;i<s.length();i++){
            t[s[i]-'a']++;
            while(1){
                int cnt=i-j+1,sum=0,mid=cnt/2+cnt%2;    //mid表示中位数所在的位置
                for(x=0;x<26;x++){
                    sum+=t[x];
                    if(sum>=mid)break;        //此时j即为中位数
                }
                sum=0,mid=x;        //计算所有字母变成中位数的次数之和
                for(x=0;x<26;x++){
                    sum+=abs(mid-x)*t[x];
                }

                if(sum<=k){            //若合法，则维护该区间长度最大值
                    ma=max(ma,i-j+1);
                    break;
                }
                t[s[j]-'a']--;
                j++;
            }
        }
        return ma;
}