首页 > 代码库 > 51Nod - 1127 最短的包含字符串
51Nod - 1127 最短的包含字符串
51Nod - 1127 最短的包含字符串
给出一个字符串，求该字符串的一个子串S，S包含A-Z中的全部字母，并且S是所有符合条件的子串中最短的，输出S的长度。如果给出的字符串中并不包括A-Z中的全部字母，则输出No Solution。
Input
第1行，1个字符串。字符串的长度 <= 100000。
Output
输出包含A-Z的最短子串长度。如果没有符合条件的子串，则输出No Solution。
Input示例
BVCABCDEFFGHIJKLMMNOPQRSTUVWXZYZZ
Output示例
28
题解：
双指针 + 计数数组，可以在 O(n ) 时间内解决。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN = 100000 + 5;
int vis[26];
char ch[MAXN];
int main(){
freopen("in.txt", "r", stdin);
int len, cnt, i, j, ans;
while(scanf("%s", ch) != EOF){
getchar();
len = strlen(ch);
memset(vis, 0, sizeof(vis));
i = 0; j = 0; ans = len + 1; cnt = 0;
while(j < len){
if(vis[ch[j] - ‘A‘] == 0){
cnt += 1;
}
vis[ch[j] - ‘A‘] += 1;
j++;
if(cnt == 26){
while( i<j && vis[ch[i] - ‘A‘] > 1){
vis[ch[i] - ‘A‘] -= 1;
i++;
}
if( ans > (j - i) ){
ans = j - i;
}
}
}
if(ans == len + 1){
printf("No Solution\n");
}else{
printf("%d\n", ans );
}
}
return 0;
}
51Nod - 1127 最短的包含字符串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。