题目描述
给定一个由小写字母构成的字符串 s。
字符 c 被称为字符串 s 的 k 显性字符,当且仅当字符串 s 的所有长度不小于 k 的子串都包含字符 c。
对于给定的字符串 s,请你找到一个最小的 k,使得 s 中至少存在一个 k 显性字符。
样例
输入样例1:
abacaba
输出样例1:
2
输入样例2:
zzzzz
输出样例2:
1
输入样例3:
abcde
输出样例3:
3
C++ 代码
/寻找相同字符的非连续间隔、该字符首次出现的位置与串头的距离和该字符最后出现的位置与字符串尾的距离 中的最大值
再找到所有字符的此值的最小值/
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
int dp[26];
string s;
int main()
{
int flag=0;
cin>>s;
int l=s.length()-1;
int ress=INT_MAX,cnt=0;
for(int i=0;i<=25;i)
{
dp[i]=0;
int t=0;
for(int j=0;j<s.length();j)
{
if(s[j]==i+’a’)
{
if(dp[i]==0) //如果是第一次发现此字符 记录串头到此字符下标的距离。
{
cnt++; // 记录是否所有字符都相同
dp[i]=j+1;
t=j;
continue;
}
else
{
flag=1; //记录是否所有字符都不相同
if(j-t!=1)
dp[i]=max(dp[i],j-t); //记录相同字符 非连续的间隔的最小值
t=j;
}
}
}
dp[i]=max(dp[i],l-t+1); // 此字符最后出现的位置 到字符串尾的距离也要参与DP
ress=min(dp[i],ress);
}
if(cnt<=1) cout<<1<<endl; //如果所有字符相同输出1
else if(flag==0) cout<<(l+1)/2+1<<endl; //如果所有字符都不相同 则输出字符串长度的一半 向上取整
else cout<<ress<<endl; //正常情况则输出结果
return 0;
}
大佬代码块都不使一下嘛,这样阅读起来很困难呀