CF888C K-Dominant Character

888，多么吉利的数字

K-Dominant Character

题目大意

有一个由小写字母构成的字符串 $s$ （ $|s| \le 10^5$ ），当一个字符 $c$ 在 $s$ 的任意一个长度不超过 $k$ 的子串中都存在时，就称 $c$ 为 $s$ 的“k-dominant character”

现在要求一个最小的 $k$ 使得存在 $c$ 为 $s$ 的“k-dominant character”

思路

看见 $10^5$ 想到 $n \log n$ ，不难想到二分 $k$

先看一眼答案是否满足单调性（好几次没管答案单调性就白打了半天），明显如果 $c$ 是“k-dominant character”，它也一定就是“(k + 1)-dominant character”，可见答案具有单调性，可以二分

考虑如何在 $O(n)$ 的时间内判定答案

等等

我突然想到，字符仅由小写构成，直接暴力扫描 $26$ 个字母每个字母的位置，两两之差的最大值就是这个字母作为“k-dominant character”的最小 $k$ ，注意首尾

如对于 $s = bbababaab$ ， $a$ 的位置为 $3, 5, 7, 8$ （下标从 $1$ 开始），那么 $a$ 作为“k-dominant character”的最小 $k$ 就是 $\max(3 - 0, 5 - 3, 7 - 5, 8 - 7, |s| + 1 - 8) = 3$

时间复杂度 $O(26 \times n) = O(n)$

然后就AC了……diao，说好的二分呢！

代码

#include <bits/stdc++.h>
#define STC static
using namespace std;
const int N = 1e5 + 5;

int main()
{
    STC char s[N];
    scanf("%s", s + 1);
    int n = strlen(s + 1), last, ans = n, as;
    for (char ch = 'a'; ch <= 'z'; ++ch)
    {
        last = as = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (s[i] == ch)
                as = max(as, i - last), last = i;
        }
        as = max(as, n + 1 - last);
        ans = min(ans, as);
    }
    printf("%d\n", ans);
    return 0;
}