CF888C题解

• 分析

  容易想到可以枚举每个字母，分别求其最小 \(k\) 取 \(\min\)。
  思考对于一个 \(k\)，如何判其不合法。容易想到如果存在一个没有这个字符的长度大于等于 \(k\) 的子段，那么这个 \(k\) 就不合法。
  那么我们就知道如何求最小合法 \(k\) 了。找到最长的没有这个字符的子段，其长度加一即为 \(k\)。

• 代码

#include <iostream>
using namespace std;
constexpr int MAXN(1000007);
constexpr int INF(0x3f3f3f3f);
string s;
int res(INF);
inline void read(int &temp) { cin >> temp; }
int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> s;
	for (char i('a'); i <= 'z'; ++i) {
		int lst(-1), ans(0);
		for (int j(0); j < (int)s.length(); ++j)  if (s[j] == i)  ans = max(ans, j - lst - 1), lst = j;
		ans = max(ans, (int)s.length() - lst - 1);
		res = min(res, ans + 1);
	}
	cout << res << endl;
	return 0;
}