鏈接 :?

Problem - C - Codeforces

題意 :?

輸入一個長度 ≤1e5 的字符串 s，只包含小寫字母。
找到一個最小的 k，使得所有長度 >= k 的連續子串，有公共字母（這些子串的交集不為空）。
?

思路 :?

就是求每個字母的相鄰距離的最大值，然后求這些最大值的最小值;

代碼 :?

#include<bits/stdc++.h>
using namespace std; 
int main(){string s ; cin >> s;// 每個字母的最大間隔int ans = INT_MAX , n = s.size();map<int,vector<int>> a;for(int i=0;i<n;i++)a[(int)(s[i]-'a')].push_back(i);for(int i=0;i<26;i++){int len = a[i].size() , ma = 0 ;a[i].push_back(n);if(len) ma = a[i][0]+1;else continue;for(int j=1;j<=len;j++) ma = max(ma,a[i][j]-a[i][j-1]);ans = min(ma,ans);// 求最小值 }cout << ans << endl;
}

代碼(優化)

用a來記錄每個字母之前出現的位置，b記錄每個字母的距離的最大值；

#include<bits/stdc++.h>
using namespace std;
int a[26],b[26];
int main(){string s ; cin >> s;for(int i=0;i<26;i++) a[i] = -1;int ans = INT_MAX , n = s.size();for(int i=0;i<n;i++){int t = s[i]-'a';b[t] = max(i-a[t],b[t]);a[t] = i;} for(int i=0;i<26;i++)if(a[i]!=-1)ans = min(ans , max(b[i],n-a[i]));cout << ans << endl;
}