ZYF008 最短字符串
大约 1 分钟
ZYF008 最短字符串
【算法】 双指针、滑动窗口
【C++】 双指针、字符串、cnt数组
【难度】 普及−
一、题目简述
给定字符串 (含大小写字母),找最短子串包含 中所有种类的字母(区分大小写)。输出最小长度。
二、解题思路
先统计 中一共有多少种不同字母(totalKinds)。
滑动窗口维护当前子串中各字母出现次数和不同种类数。
- 右移,加入字符
- 当窗口内种类数 ==
totalKinds,尝试收缩 - 记录最短长度
区分大小写:'A'-'Z' 和 'a'-'z' 的 ASCII 不同,用 cnt[128] 即可。
手动模拟 "AaA", n=3:
- 不同种类:'A'(65) 和 'a'(97),共 2 种
- r=1('A'): kinds=1
- r=2('a'): kinds=2,ans=2
- 收缩 l=1 移除 'A' → kinds=1,不能继续
- 最短=2
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int cnt[128]; // ASCII 覆盖大小写
int main() {
int n;
string s;
cin >> n >> s;
// 统计总共有多少种字母
int totalKinds = 0;
bool has[128] = {false};
for (char c : s) {
if (!has[(int)c]) { has[(int)c] = true; totalKinds++; }
}
int l = 0, kinds = 0, ans = n;
for (int r = 0; r < n; r++) {
int idx = (int)s[r];
if (cnt[idx] == 0) kinds++;
cnt[idx]++;
while (kinds == totalKinds) {
ans = min(ans, r - l + 1);
int leftIdx = (int)s[l];
cnt[leftIdx]--;
if (cnt[leftIdx] == 0) kinds--;
l++;
}
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。每个字符最多进出窗口一次。
- 空间复杂度: 额外空间(
cnt[128]和has[128]为固定大小)。
