Codeforces 888C K-Dominant Character 9（思維）

題目描述：

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.

Example

Input

abacaba

Output

2

Input

zzzzz

Output

1

Input

abcde

Output

3

題意：給定一字元串s，其長度為k(1<=k<=s)的任意子串裡都包含同一字母c，求滿足該條件的最小的k

思路：開始想的很複雜。其實對于每個字母，我們隻考慮串中和它相同的字母即可。用一個數組儲存該字母上一次出現的位置。再用一個數組更新該字母每兩個之間距離的最大值。再取所有種類字母的間隔最大值的最小的那個就是答案。

要注意最前面和最末尾都要假定有與目前字母相同的一個字母，如樣例3。

比如樣例1，abacaba，字母a間隔的最大值是2，b是4，c是4.取裡面的最小值為a的2.

對于樣例3，因為我們假定最前面和最末尾都有相同的字母，這樣對于字母c，串變為cabcdec，求出c的為3，其他為4、5.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[100005];
int last[26],ans[26],n;
void solve()
{
	memset(last,-1,sizeof(last));
	memset(ans,-1,sizeof(ans));
	n=strlen(s);
	
	int i,j,t;
	for(i=0;i<n;i++)
	{
		t=s[i]-'a';
		if(last[t]==-1)
		{
			last[t]=i;
			ans[t]=max(ans[t],i+1);//假定開頭有與目前相同字母
		}
		else
		{
			ans[t]=max(ans[t],i-last[t]);
			last[t]=i;
		}
	}
	for(i=0;i<26;i++)//假定串最後面有與目前相同字母
	{
		if(last[t]!=-1)
		ans[i]=max(ans[i],n-last[i]);
	}
	sort(ans,ans+26);
	for(i=0;i<26;i++)
	if(ans[i]!=-1)
	{
		cout<<ans[i]<<endl;
		break;
	}
}
int main()
{
	while(cin>>s)
	{
		solve();
	}
	return 0;
}