Codeforces 888C - K-Dominant Character
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.
範例:
input:
1 | abacaba |
output:
1 | 2 |
input:
1 | zzzzz |
output:
1 | 1 |
input:
1 | abcde |
output:
1 | 3 |
題意:
給你一個字串，當所有長度為K的子字串都有至少一個共同字元c時，則c在此字串中稱為K-Dominant 。現在c未定，但至少要有一個c存在K-Dominant ，問你K最小可以是多少？
思路:
用二分搜尋法依照規則搜尋子字串長度。