平顶山做网站多少钱,天河建网站,设计平面广告公司,wordpress 整站带数据题意
让我们在这个字符串中找一定k长度的字串中都至少含有一个相同的字符 让求这个字串的最小长度
分析
也就是说当我们最终确定了 字串的最小长度后 每个以此长度的字串都至少含有一个相同字符 那么当我们找这个长度的时候 也就是说 每个k长度的字串中都至少出现一个相同的…题意
让我们在这个字符串中找一定k长度的字串中都至少含有一个相同的字符 让求这个字串的最小长度
分析
也就是说当我们最终确定了 字串的最小长度后 每个以此长度的字串都至少含有一个相同字符 那么当我们找这个长度的时候 也就是说 每个k长度的字串中都至少出现一个相同的字符 那么也就是说 如果我们知道每个字符间距的最大距离作为这个串的必要结果 也就是说 这个所有字符最大间距的最小值就是我们需要的答案
code
#includebits/stdc.h
using namespace std;
typedef long long ll;
char a[100010];
int pos[30],ans[30];// pos存放最长距离 ans中存放每个字符的最大距离 其中取最小的就是结果
const int inf 900010;
int main()
{gets(a);int c0,len strlen(a);memset(ans,-1,sizeof(ans));for(int i0;ilen;i){// 注意考虑的是每个字符的最大间距 不能忽略一个字符最后的位置和最后长度的距离 和一个字符第一个位置与最开始位置的长度 我们考虑的是if(ans[a[i]-a]-1)ans[a[i]-a] i1;//b与串开始的距离 为最大距离ans[a[i]-a]max(i-pos[a[i]-a],ans[a[i]-a]);// 注意 aaabbb的情况中要考虑到a与最后一个字符的距离 pos[a[i]-a]i;}for(int i0;i26;i)if(ans[i]!-1)ans[i] max(len-pos[i],ans[i]);int resinf;for(int i0;i26;i){if(ans[i]!-1)res min(ans[i],res);}printf(%d\n,res);return 0;
}
