[题解] String I

考察知识点：字符串操作，枚举，二分

首先，我们不难发现朴素算法：

• 枚举答案串长度
• 检验所有长度为该长度的串变为26个字母需要的操作数量
• 然后回答即可

事实上，该算法在某些处理速度较快的语言中可以通过，时间复杂度为。

然而，将枚举改为二分，时间复杂度即可降为，可以轻松通过本题。

参考代码：

class Solution {
public:
    int k;
    string s;
    inline bool check(int len)
    {
        for (int j = 1; j <= 26; ++j) {
            int ret = 0;
            for (int i = 0; i < len; ++i) {
                ret += abs(s[i] - ('a' + j - 1));
            }
            if (ret <= k) return true;
            for (int i = len; i < s.length(); ++i) {
                ret += abs(s[i] - ('a' + j - 1));
                ret -= abs(s[i - len] - ('a' + j - 1));
                if (ret <= k) return true;
            }
        }
        return false;
    }
    int string1(int K, string S) {
        k = K, s = S;
        int l = 1, r = s.length(), mid, ans = 0;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (check(mid) == true) l = mid + 1, ans = mid;
            else r = mid - 1;
        }
        return ans;
    }
};