B4240 [海淀区小学组 2025] 最短字符串

chen_zhe · 2025-03-11 10:58:46 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

本题考察双指针、滑动窗口。

想象这么一个流程：我们使用两个变量 l,r 来框选住一个区间 [l,r]，要求让 [l,r] 框选住所有出现过的字母。为此，我们可以这样做：

• 首先让 l=1，r 从 1 开始不断往右扩展，记录下是否每种字母都出现过；
• 若已经每种字母都出现过了，则让 l 往右移动，直到区间 [l,r] 内的字母种类减少；
• 再向右扩展 r，直到每种字母都出现过，返回上一步；
• 直到当 r=n，l 无法向右为止。

这样我们就动态地维护了含有所有种类字母的区间 [l,r]。选择其中区间长度最短的区间则为答案。

参考代码：

// 起初需要使用一重循环知道字符串中有多少种字母 tot，代码略。
for(R = 1; R <= n; R++){
    char c = S[R];
    freq[c]++; // 增加字符 c 的出现次数（纳入区间）
    if(freq[c] == 1)
        cnt++; // 种类数增加
    // 当区间内包含所有种类时，尝试缩小区间
    while(cnt == tot && L <= R){
        if(R - L + 1 < ans) // 更新答案
            ans = R - L + 1;
        char d = S[L];
        freq[d]--; // 减少字符 d 的出现次数（移出区间）
        if(freq[d] == 0)
            cnt--; // 种类数减少
        L++;
    }
}