NC18386 字符串
字符串
https://ac.nowcoder.com/acm/problem/18386
题目描述:
给定一个字符串S,求包含全部26个小写字母的字串的最短长度。
输入描述:
一行一个字符串S。只包含小写字母。S的长度不超过1e6.
输出描述:
一行一个数字,代表最短长度。数据保证存在一个合法的S的子串。
题目分析:
双指针(尺取法)即可
设置l和r两个指针,起初l=r=0,然后r指针不断向右移动,同时用一个数组num[26]统计r走过的字符串里面每种小写字母的个数,当满足26种字母都存在时,即可移动l指针,同时减去l指针路过的字符串中的字母个数,在所有满足条件的r-l+1种去最小值,即为本题答案。
Code:
#include<iostream> #include<cstdio> #include<vector> #include<cmath> #include<string> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<set> #define endl '\n' #define all(s) s.begin(),s.end() #define lowbit(x) (x&-x) #define rep(i,a,n) for (int i=a;i<=n;i++) #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define mem(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define pb push_back #define pi acos(-1.0) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int mod=1e9+7; const double eps=1e-8; const int inf=0x3f3f3f3f; const int N=2e5+10; int num[26]; int l,r; bool ok() { for(int i=0;i<26;i++) if(!num[i]) return false; return true; } int main() { int n,m,q,k; string s; cin>>s; int ans=inf; for(int i=0;i<s.length();i++){ r=i; num[s[r]-'a']++; while(ok()){ ans=min(ans,r-l+1); num[s[l]-'a']--; l++; } } cout<<ans; }