题目描述
给定一个由小写字母构成的字符串 s。
字符 c 被称为字符串 s 的 k 显性字符,当且仅当字符串 s 的所有长度不小于 k 的子串都包含字符 c。
对于给定的字符串 s,请你找到一个最小的 k,使得 s 中至少存在一个 k 显性字符。
输入格式
一个由小写字母构成的字符串 s。
输出格式
一个整数,表示 k 的最小可能值。
数据范围
前 6 个测试点满足 1≤|s|≤10。
所有测试点满足 1≤|s|≤105
样例
abacaba
算法1
(暴力枚举) $O(n)$
计数,记下出现间隔,最大的间隔就是该字符中k最小的情况(不要忘记头和尾),在扫描所有字符
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string a;
int b[26][111111],k[26],l=2e9;
int main()
{
cin>>a;
int kk=a.size();
for (int i = 0; i < a.size(); i ++ ){
int t=a[i]-'a';
b[t][++k[t]]=i;
}
for (int i = 0; i < 26; i ++ ){
int ans=b[i][1]+1;
for (int j = 2; j <= k[i]; j ++ ){
ans=max(ans,b[i][j]-b[i][j-1]);
}
ans=max(ans,kk-b[i][k[i]]);
l=min(l,ans);
}
cout<<l;
}