CodeForces 888C. K-Dominant Character（思维）

problem description

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】
2
1
2
3
4

【input】
zzzz
【output】
1
1
2
3
4

【input】
abcde
【output】
1
1
2
3
4

---

题意

给定一个仅由小写字母组成的字符串，任意选定一个字符 k ，将字符串分成若干个子串，求出子串的最短长度，使得每个子串都至少包含一个字符 k 。

---

思路

因为每个子串都要包含至少一个字符 k ，那么相同的字符 k 之间的距离就要尽可能的大，这样才能使得子串的长度尽可能的短。

由于字符串仅由小写字母组成，所以可以依次遍历每种字符，找出相邻的同一字符之间的最大距离 len，再比较找出不同字符中 len 的最小值，即为子串的最短长度。

如果整个字符串均由同一字符组成，则答案为 1 ;

如果整个字符串均由不同字符组成，则答案为 s.size() / 2 + 1 .

---

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 1e5 + 10;

int main()
{
    string s;
    cin >> s;

    set<char> st; //存储字符的种类
    
    int n = s.size();
    for (int i = 0; i < n; i++)
        st.insert(s[i]);

    int mn = 1e8;
    for (char i = 'a'; i <= 'z'; i++){
        int len = 1;
        int mx = 0;
        for (int j = 0; j < n; j++){
            if (s[j] == i){
                len = 1;
            }
            else 
                len++;

            mx = max(mx, len); //相同且相同字符的最大距离
        }

        mn = min(mn, mx); //最大距离里面的最小距离
    }

    if (st.size() == 1)
        cout << 1 << endl;
    else if (st.size() == n)
        cout << n / 2 + 1 << endl;
    else {
        cout << mn << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

---