你可能见过下⾯这⼀句英⽂: “The quick brown fox jumps over the lazy dog.” 短短的⼀句话就包含了所有 26 个英⽂字母!因此这句话⼴泛地⽤于字体效果的展⽰。更短的还有: “The five boxing wizards jump quickly.” 所以你很好奇:还有没有更多这样包含所有 26 个英⽂字母的句⼦?于是你⽤爬⾍在互联⽹上爬取了许多英⽂⽂本,并且提取出了其中的单词。你现在希望从⼀个很长的单词序列中找出⼀段连续出现的单词,它满⾜: 所有 26 个英⽂字母都⾄少出现⼀次; 长度尽可能短,即包含的字母总数尽可能少。 输出你找到的单词序列中的字母总数。c++代码
时间: 2024-02-25 08:54:44 浏览: 216
以下是C++代码实现:
```c++
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
const int MAXN = 1e6 + 5;
int n, len;
string s;
int cnt[26];
unordered_set<char> st;
bool check() {
for (int i = 0; i < 26; i++) {
if (cnt[i] == 0 && st.count('a' + i))
return false;
}
return true;
}
int main() {
cin >> n >> s;
len = s.size();
int ans = MAXN, l = 0, r = 0;
while (r < len) {
while (r < len && !check()) {
cnt[s[r] - 'a']++;
st.insert(s[r]);
r++;
}
if (check()) {
ans = min(ans, r - l);
}
cnt[s[l] - 'a']--;
st.erase(s[l]);
l++;
}
cout << ans << endl;
return 0;
}
```
思路:
1. 用双指针维护一个区间 [l, r],初始时 l = r = 0。
2. 当区间中的所有字母都至少出现过一次时,记录当前区间长度,并将 l 右移,直到区间不再满足条件。
3. 将 r 右移,直到区间再次满足条件。
4. 重复步骤 2、3,直到 r 超出字符串范围。
5. 输出最短的满足条件的区间长度。
时间复杂度:O(n)。
阅读全文
相关推荐



















