形式化题目

给定长度为 $n$ 的字符串 $S$（只含小写字母）、两个小写字母 $c_1, c_2$ 和整数 $K$，求满足以下全部条件的连续子串 $S[i..j]$ 的个数：

1. 长度 $j - i + 1 \geqslant K$；
2. 首字符 $S[i] = c_1$；
3. 尾字符 $S[j] = c_2$。

其中 $2 \leqslant K \leqslant n \leqslant 5 \times 10^5$。$c_1$ 与 $c_2$ 可以相同；答案唯一，不存在多解。

把长度条件展开成对下标的不等式，题目等价于统计下标对 $(i, j)$ 的个数：

$n = 5 \times 10^5$ 时长度满足条件的下标对最多约 $\frac{n^2}{2} = 1.25 \times 10^{11}$ 对，这个数量级正是本题全部难度的来源。

暴力解法

思路

照着定义做：枚举左端点 $i$，再枚举右端点 $j$，逐对检查长度是否够、两个端点字符是否匹配，匹配就计数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-03 11:36
 * update_at: 2026-10-03 11:36
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 直接按定义枚举所有子串：左端点 i、右端点 j，
// 只要长度 j - i + 1 >= K 且 s[i] == c1 且 s[j] == c2 就计数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 5005;

int K;
int n;
char s[maxn];
char c1, c2;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> K;
    cin >> (s + 1) >> c1 >> c2;
    n = (int)strlen(s + 1);

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (j - i + 1 < K) {
                continue; // 长度不够，不配使用简写
            }
            if (s[i] == c1 && s[j] == c2) {
                ans++;
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

两层循环都是 $O(n)$，总时间 $O(n^2)$，空间 $O(n)$（仅存字符串本身）。

瓶颈

$n = 5 \times 10^5$ 时需要约 $6 \times 10^{10}$ 次内层判定，必然超时。

瓶颈具体在哪里？看内层循环在做什么：对固定的 $i$，我们把 $j$ 从 $i$ 一路推到 $n$，每次重新检查一遍 s[i] == c1。而这个检查对同一行的所有 $j$ 答案是完全一样的。也就是说，同一个 $c_1$ 位置被它后面的每一个 $c_2$ 位置重复统计了一次。

反过来想：如果固定右端点 $j$，那么“所有满足长度条件的 $i$”是固定的一批，我们完全可以一次把这一批里 $c_1$ 的个数数好、给所有 $c_2$ 位置复用，而不是每次重新扫描一遍。

正解

关键观察

固定右端点 $j$ 后，左端点 $i$ 满足长度条件当且仅当

所以当前所有合法起点恰好是一个前缀 $[1,\ j-K+1]$，而与 $i$ 具体的取值无关。于是

每个合法子串都有唯一的右端点 $j$，按右端点归类既不重也不漏。

再看这个前缀怎么变化：$j$ 增大 $1$，上界 $j-K+1$ 也增大 $1$。所以前缀只扩张、不收缩，每步只多解锁一个位置 $i = j-K+1$。这就是本题最关键的结构——“窗口只进不出”，于是不需要真正的双指针，一个计数器就够了。

思路

设 $\text{cnt}$ 表示当前已解锁范围内的 $c_1$ 个数，即 $\#\{\,i \in [1,\ j-K+1] \mid S[i]=c_1\,\}$。按 $j$ 从小到大扫描：

1. 先解锁：检查刚进入范围的位置 $i = j - K + 1$，若 s[j-K+1] == c1 则 cnt++；
2. 再统计：若 s[j] == c2，则以 $j$ 结尾的合法子串全部以这 cnt 个位置为起点，ans += cnt；否则以 $j$ 结尾没有合法子串，不加。

第 1 步必须排在第 2 步之前：位置 $j-K+1$ 就是当前 $j$ 的合法起点之一，本轮就该参与计数。

循环可以从 $j = K$ 开始：$j < K$ 时 $j-K+1 \leqslant 0$，合法起点集合为空，跳过它们不会有任何遗漏，还顺带避免了下标 $\leqslant 0$ 的越界访问。

用样例检验一遍。 $S = \texttt{abababdb}$，$K = 4$，$c_1 = \texttt a$，$c_2 = \texttt b$，则 $n = 8$：

以 $j=6$ 为例：此时 cnt = 2，说明合法起点有 $i=1$（S[1..6] = ababab）和 $i=3$（S[3..6] = abab）；S[6] = b 命中 $c_2$，于是答案增加 2。以 $j=8$ 为例：cnt = 3，对应 $i=1,3,5$，恰好就是题面样例说明里列出的 [abababdb]、ab[ababdb]、abab[abdb] 三个。最终 $1+2+3 = 6$，与样例一致。

正确性说明。

• 计数语义：对 $j$ 做归纳。循环开始前 $j = K-1$，上界为 $0$，集合为空，cnt = 0 成立；进入第 $j$ 轮后，集合从 $[1, j-K]$ 扩展为 $[1, j-K+1]$，新增的恰是位置 $j-K+1$，代码只对它做了一次判定，故 cnt 恒等于定义值。
• 不重不漏：任意合法子串由它的右端点 $j$ 唯一确定，它在第 $j$ 轮被计入当且仅当 $S[j]=c_2$、$S[i]=c_1$ 且 $i \leqslant j-K+1$，这正是合法性的定义。
• 两者合起来，ans 恰好等于答案。

溢出与边界提醒。

• 答案上界约为 $\frac{n(n-1)}{2} \approx 1.25 \times 10^{11}$，int 装不下，ans 必须用 long long。
• $c_1 = c_2$ 时不需要特判：起点与终点是两个独立判定，同一个位置可以既作起点又作终点；又因为 $K \geqslant 2$，起点上界 $j-K+1 \leqslant j-1 < j$，起点永远在终点左边，不会出现“自己配自己”的非法计数。
• $c_1$ 不出现在 $S$ 中时 cnt 恒为 0，输出 0，符合预期。
• $K = n$ 时循环只执行 $j = n$ 一次，只解锁位置 1，同样正确。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-03 11:36
 * update_at: 2026-10-03 11:36
 */
// P9244 [蓝桥杯 2023 省 B] 子串简写
// 正解：枚举右端点 j，用变量 cnt 维护“左侧所有满足 c1 且 j - i + 1 >= K 的起点 i 的个数”。
//         每当 j 右移一位，就新允许一个起点，把它加入 cnt。
//         若 S[j] == c2，则这 cnt 个起点各对应一个合法子串，累加进答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int maxn = 5e5 + 5;

int K;          // 子串长度下限：长度 >= K 才可以使用简写
int n;          // 字符串长度
char s[maxn];   // 原字符串，下标从 1 开始
char c1, c2;    // 要求的首字符与尾字符

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> K;
    cin >> (s + 1) >> c1 >> c2;
    n = (int)strlen(s + 1);

    ll ans = 0;
    ll cnt = 0; // 在当前右端点 j 下，左侧可作为起点的位置个数

    // j = K 是长度刚好等于 K 的最小右端点；j < K 时任何子串都不够长
    for (int j = K; j <= n; j++) {
        // 右端点从 j-1 变成 j 时，起点 i = j - K + 1 的长度由 K-1 变成 K，
        // 正好刚刚够长，于是它被“解锁”，加入可选起点集合
        if (s[j - K + 1] == c1) {
            cnt++;
        }
        // 现在 cnt 里恰好是 [1, j-K+1] 中所有值为 c1 的位置，且全部满足长度条件
        if (s[j] == c2) {
            ans += cnt;
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

时间：j 从 $K$ 扫到 $n$，每轮两次 $O(1)$ 比较，共 $O(n)$；$n = 5 \times 10^5$ 时约 $5 \times 10^5$ 次操作。

空间：除输入字符串 $O(n)$ 外，只用了 cnt、ans 两个变量，额外空间 $O(1)$。不需要前缀和数组，也不需要二分。

总结

本题的推导链条是：

1. 换枚举顺序：从“先定左端点、再扫右端点”变成“先定右端点、回头找左端点”；
2. 发现结构：固定 $j$ 后合法起点恰好是一个前缀，而这个前缀随 $j$ 增大“只进不出”；
3. 用计数器替代扫描：只进不出的结构不需要滑动窗口的删除操作，一个变量就能维护统计量。

第一步是这类计数题最常用的角度切换——要让被重复计算的量变得可复用。第二步是识别“单调窗口”。第三步是本题比一般双指针更简单的地方：因为窗口只扩张，连左指针都不用维护。

实现上要留心两点：

• 先解锁、后统计，顺序反了会漏掉长度恰好等于 $K$ 的那些子串；
• 答案要用 64 位整数，最多约 $1.25 \times 10^{11}$。

（暴力解法与正解的输出已在 20 组随机数据上逐一比对一致。）