Educational Codeforces Round 32 C. K-Dominant Character（模拟）-蒲公英云

Educational Codeforces Round 32 C. K-Dominant Character（模拟）

叁歲伎倆 2022-06-06 13:25 269阅读 0赞

C. K-Dominant Character

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a string s consisting of lowercase Latin letters. Character c is called k-dominant iff each substring of s with length at least kcontains this character c.

You have to find minimum k such that there exists at least one k-dominant character.

Input

The first line contains string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 100000).

Output

Print one number — the minimum value of k such that there exists at least one k-dominant character.

Examples

input

abacaba

output

input

zzzzz

output

input

abcde

output

题解：

题意：

让你找一个最小的长度k，使得所有子串中存在一个相同的字符c

有点意思的一题，我的思路是记录下两个相同字符的最长距离，然后取这些距离的最小值就行了

代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
#define lson k*2
#define rson k*2+1
#define M (t[k].l+t[k].r)/2
#define ll long long
#define INF 10086111
int a[30];
int b[30];
int c[30];
int main()
{
    char s[100005];
    int i,t;
    memset(b,0,sizeof(b));
    for(i=0;i<26;i++)
        a[i]=-1;
    memset(c,0,sizeof(c));
    scanf("%s",s);
    for(i=0;s[i];i++)
    {
        t=s[i]-'a';
        b[t]=max(b[t],i-a[t]);
        a[t]=i;
        c[t]++;
    }
    for(i=0;i<26;i++)
    {
        int temp=strlen(s)-a[i];
        if(c[i])
            b[i]=max(b[i],temp);
    }
    int minn=1008611;
    for(i=0;i<26;i++)
    {
        if(c[i]!=0)
            minn=min(minn,b[i]);
    }
    printf("%d\n",minn);
    return 0;
}