分享一下自己的思路，仅供参考，希望可以帮到大家

算法1(24分)

(暴力枚举) O(n^2)

我们首先不考虑优化，怎么找到答案？

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

LL ans = 0;
//我们发现字串的长度是5e5,极端情况，前250000全是c1,后一半全是c2
//ans最大可能为125 * 1e8,而int最大约21亿（2.1 * 1e9）,爆int,开long long
int main()
{
    int k;
    char c1,c2;
    string s;

    cin >> k >> s >> c1 >> c2;

    for(int i = 0;i < s.size() ;i++)
    {
        if(i + k > s.size())continue;
        if(s[i] == c1)
        {
            for(int j = i + k - 1;j < s.size();j++)
            {
                if(s[j] == c2)
                {
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

考虑优化

前置知识（前缀和）这是一个 前缀和讲解 的例子。

我们不难发现，我们枚举j的时候，需要的是下标从j开始到结尾，所有字符值为c2的数量，那么我们倒着求前缀和，开一个新数组cnt[N],返回当前下标开始c2的数量

for(int i = 0;i < s.size();i++)
{
    if(s[i] == c2)
    {
        cnt[i] = 1;
    }
}

for(int i = N - 1;i >= 0;i--)
    cnt[i] = cnt[i] + cnt[i + 1];

这样我们可以优化掉一层循环时间复杂度时间降到O(n)

具体的AC代码需要自己整合，不给大家直接放出来了