牛客网14778题：滑动窗口巧解字符串最大连续子串问题

一、题目解读

牛客网14778题要求我们找到一个字符串中通过最多修改m个字符后，能够获得的最长连续相同字符子串的长度。题目考察了滑动窗口算法的实际应用，是字符串处理类问题的经典题型。

二、解题思路

采用滑动窗口(双指针)算法，核心思想是：

1. 维护一个可变窗口，统计窗口中非目标字符的数量

2. 当替换成本超过m时，移动左指针缩小窗口

3. 始终保持窗口内替换成本不超过m，同时记录最大窗口大小

三、解题步骤

1. 初始化左右指针left和right都指向字符串开头

2. 右指针right逐步向右移动扩展窗口

3. 遇到非目标字符时增加替换成本cost

4. 当cost超过m时，移动左指针left直到cost≤m

5. 每次窗口变动后更新最大长度max_len

6. 分别对'a'和'b'两种字符进行计算，取最大值

四、完整代码实现

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int solve(const string &s, int m, char target) {
    int left = 0, max_len = 0, cost = 0;
    for (int right = 0; right < s.size(); ++right) {
        if (s[right] != target) cost++;
        while (cost > m) {
            if (s[left] != target) cost--;
            left++;
        }
        max_len = max(max_len, right - left + 1);
    }
    return max_len;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    string s;
    cin >> n >> m >> s;
    
    // 分别计算全a和全b两种情况的最大长度
    int max_a = solve(s, m, 'a');
    int max_b = solve(s, m, 'b');
    
    cout << max(max_a, max_b) << endl;
    return 0;
}

五、总结

本题展示了滑动窗口算法在字符串处理中的典型应用，通过维护一个满足条件的可变窗口，我们能够在O(n)时间复杂度内解决问题。该算法思想也可应用于其他类似的最大连续子串问题。