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

叁歲伎倆 2022-06-06 13:25 136阅读 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 *k*contains 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;
    }