自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:18:03，当前版本为作者最后更新于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++;
    }
}