牛客14778题解析：滑动窗口算法破解字符替换问题的最优解

一、题目解读

牛客14778题要求给定字符串s、替换次数上限m及目标字符，求解在s中通过最多m次替换操作，得到的最长连续子串长度。例如，当s="abcbab"，m=2，target='a'时，需将'b'替换为'a'，最终得到"abcaab"，子串长度为5。题目核心在于平衡替换次数与子串长度，需高效算法解决。

二、解题思路

采用滑动窗口 + 双指针策略。通过维护左右指针动态调整窗口大小，实时统计替换次数：

1. 右指针右移时，若遇到非目标字符则增加替换次数；

2. 当替换次数超m时，左指针右移缩减窗口，同时减少替换计数；

3. 实时更新窗口内最长长度。

该思路巧妙将替换次数与子串范围关联，避免暴力枚举，时间复杂度降为O(n)。

三、解题步骤详解

1. 初始化变量：left=0（左指针），max_len=0（最长长度），cost=0（当前替换次数）。

2. 右指针遍历：每移动一次，若当前字符≠target，则cost++。

3. 动态调整窗口：当cost>m时，左指针右移并递减cost（若移出字符非target）。

4. 更新结果：每次窗口调整完成后，计算right-left+1与max_len的较大值。

5. 双目标求解：主函数中分别调用solve()计算全a和全b的最长长度，取两者最大值输出。

四、代码与注释

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

// 求解指定target下的最长子串长度
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++; // 非目标字符则替换次数+1
        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; // 可忽略，n无用
    string s;
    cin >> n >> m >> s; // 输入m和s
    
    int max_a = solve(s, m, 'a'); // 计算全a情况
    int max_b = solve(s, m, 'b'); // 计算全b情况
    cout << max(max_a, max_b) << endl; // 输出两者最大值
    return 0;
}

五、总结

本文代码通过滑动窗口算法，将字符替换与动态区间维护结合，高效解决牛客14778题。该解法关键点：

1. 利用双指针动态平衡替换次数与子串长度；

2. 避免冗余计算，实现线性时间复杂度；

3. 适用于同类替换限制下的最值求解场景。

掌握此思路可拓展至更多动态规划优化问题。