题解归档 - cf888C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf888C
• 本地来源：problems/cf888C/idea.md
• 题目链接：https://codeforces.com/contest/888/problem/C
• 原始标题：CF888C K-Dominant Character

思路

CF888C K-Dominant Character

题意

给定小写串 s。若字符 c 满足：所有长度 ≥ k 的子串都包含 c，则称 c 为 k-dominant。求最小的 k，使得存在至少一个 k-dominant 字符。

做法

对每个出现过的字符 c，记其出现位置为 p_0 < p_1 < ... < p_{m-1}。

不含 c 的最长连续段长度为：

$$\max\big(p_0,\; p_{i+1}-p_i-1,\; n-1-p_{m-1}\big)$$

记为 gap。则 c 成为 k-dominant 的最小 k = gap + 1（因为长度 gap+1 的子串可以避开 c，而 gap+2 不行）。

答案为所有出现字符的最小 k。复杂度 O(n)。

样例

• abacaba：a 的最大间隔为 1 → k=2
• zzzzz：间隔 0 → k=1
• abcde：c 的最大间隔为 2 → k=3

验证

• 样例 + 对拍 500 组（brute 枚举 k 与子串）

代码

来源：problems/cf888C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:40:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s;
vector<ll>pos[26];
ll n,i,j,k,zc,pd,cur,cnt,ans;
int main(){
    cin>>s;
    n=s.size();
    ans=n+1;
    for(i=0;i<n;i++) pos[s[i]-'a'].push_back(i);
    for(k=0;k<26;k++){
        if(pos[k].empty()) continue;
        zc=pos[k][0];
        pd=n-1-pos[k].back();
        cur=max(zc,pd);
        for(i=0;i+1<(ll)pos[k].size();i++) cur=max(cur,pos[k][i+1]-pos[k][i]-1);
        ans=min(ans,cur+1);
    }
    cout<<ans<<"\n";
    return 0;
}