题目描述

难度分:$1400$

输入一个长度$\leq 10^5$的字符串$s$，只包含小写字母。

找到一个最小的$k$，使得所有长度$\geq k$的连续子串，有公共字母（这些子串的交集不为空）。

输入样例$1$

abacaba

输出样例$1$

2

输入样例$2$

zzzzz

输出样例$2$

1

输入样例$3$

abcde

输出样例$3$

3

算法

差分

这种题目但凡我能用二分答案把样例测过去我都不会再想别的方法了，但是很不巧，今天二分答案样例就错了，所以想想别的办法。考虑公共字母是某个字符$c$，那要想每个子串都包括这个字符$c$，那这个子串的长度一定不能小于两个相邻$c$的最大下标差，本质上就是$c$出现所有位置的差分数组最大值。因此，只需要求所有字符$c$最大下标差的最小值即可。

实现的时候可以一边遍历$s$，一边维护一个$last$数组，$last[c]$表示$c$字符上一次的出现位置，不断维护$s[i]-last[s[i]]$的最大值，它就是字符$s[i]$的答案。为了方便地考虑两端的边界情况，可以对每个字符加两个哨兵，认为所有字符都在索引$0$位置上出现过一次，索引$n+1$位置上也出现过一次。

复杂度分析

时间复杂度

瓶颈在于遍历一遍字符串，因此时间复杂度是$O(n)$的。

空间复杂度

存储了每种字符的最后一个位置$last$，以及每种字符的答案$ans$，空间都是$O(\Sigma)$（其中$\Sigma$是字符集大小，本题中为$26$），这也是本算法的额外空间复杂度。

C++ 代码

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

using namespace std;
const int N = 100010;
int n;
char s[N];

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int last[26] = {0}, ans[26] = {0};
    for(int i = 1; i <= n; i++) {
        ans[s[i] - 'a'] = max(ans[s[i] - 'a'], i - last[s[i] - 'a']);
        last[s[i] - 'a'] = i;
    }
    int res = n;
    for(int i = 0; i < 26; i++) {
        if(ans[i]) {
            ans[i] = max(ans[i], n + 1 - last[i]);
            res = min(res, ans[i]);
        }
    }
    printf("%d\n", res);
    return 0;
}