双指针 时间复杂度O(n + m)

#include <bits/stdc++.h>
#define debug(x) cout << #x << ' ' << x << '\n'
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 500010, mod = 1e9 + 7, inf = 0x3f3f3f3f;
int n, m, k;
string s;
char A, B;
int a[N], b[N];
void solve()
{
    cin >> k;
    cin >> s >> A >> B;
    for (int i = 0; i < s.size(); i ++) {
        if (s[i] == A) {
            a[++n] = i;
        } 
        if(s[i] == B) {
            b[++m] = i;
        }
    }
    ll res = 0;
    int i = 1, j = 1;
    while(i <= n) {
        while (j <= m && b[j] - a[i] + 1 < k) j ++; 
        res += m - j + 1;
        i ++;
    }
    cout << res << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}