1.举个例子
比如有一个只有 小写字母 [a-z]组成的字符串 s
那么当 s 的长度 n>26 时,则必有两个字母是相同的。这就是鸽巢原理
先进行最不利构造,即先构造一个字母全不相同的字符串,即[a-z]刚好出现一次的串,长度为 26
比如 xyzabcdefghijklmnopqrstuvw, xyzabcdefklmnopqrstuvwghij .... 任意排列都可以
即这个是满足条件的最长序列了
然后加长度,无论加那个字母,都会出现重复的字母
2简单例题:
CF672B - Different is Good
题目要求,任意子串,包括长度为1的都不同。
考虑最不利情况,那么即是,每个字母都不相同。
然而,根据鸽巢原理可知,当n>26 时,比有两个字母相同,不满足条件,返回-1
代码如下:
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 1e5+5;
char cs[MAXN];
int cnt[26];
int n;
int main(){
cin>>n;
cin>>cs;
for(int i=0;i<n;i++){
cnt[cs[i]-'a']++;
}
int a = 0;
for(int i=0;i<26;i++){
if(cnt[i]>1){
a+= cnt[i]-1;
}
}
//根据鸽槽原理,至少2个相同
if(n>26){
cout<<-1<<endl;
return 0;
}
if(a>=26){
cout<<-1<<endl;
}else{
cout<<a<<endl;
}
return 0;
}