C. K-Dominant Character

给出一个字母串,k满足:长度至少为k的字串一定包含某字母c,求最小的k

一个数组记录每个字母上一次出现的位置,用来计算另一个数组:记录每个字母与其相邻的相同字母的最大距离(设0和len两个位置一定有相同的字母),答案就是这个数组中的最小值啦~

    me(flag, );
scanf("%s", s + );
n = strlen(s + );
For(i, , n)
{
if (!flag[s[i]])
{
lk[s[i]] = i;
q.push(s[i]);
flag[s[i]] = ;
len[s[i]] = i;
}
else
{
chkmax(len[s[i]], i - lk[s[i]]);
lk[s[i]] = i;
}
} while(!q.empty()){
int x = q.front();
q.pop();
chkmin(ans, max(len[x],n+-lk[x]));
}
cout << ans;
上一篇:poj 2251 Dungeon Master 3维bfs(水水)


下一篇:整数m去掉n位后剩下最大(小)值