字符串(尺取法)
字符串
https://ac.nowcoder.com/acm/problem/18386
題目描述:
給一字符串,選出一段區(qū)間包含26個(gè)小寫字母,求最短區(qū)間長(zhǎng)度
Slove:
用尺取法,從l=r=1開始,如果【l,r】中不足26個(gè)小寫字母 r++,否則 先記錄答案,然后l++;
代碼
#include <map> #include <set> #include <cmath> #include <stack> #include <queue> #include <cstdio> #include <bitset> #include <vector> #include <iomanip> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> #include <unordered_map> #define UpMing main #define re register #pragma GCC optimize(2) #define Accept return 0; #define lowbit(x) ((x)&(-(x))) #define mst(x, a) memset( x,a,sizeof(x) ) #define rep(i,a,b) for(int i=(a);i<=(b);++i) #define dep(i,a,b) for(int i=(a);i>=(b);--i) using namespace std; typedef long long ll; typedef pair<int,int> PII; typedef unsigned long long ull; const int inf =0x3f3f3f3f; const int maxn=1e6+7; const ll mod = 1e9+7; const int N =1e6+3; inline ll read() { ll x=0; bool f=0; char ch=getchar(); while (ch<'0'||'9'<ch) f|=ch=='-', ch=getchar(); while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar(); return f?-x:x; } void out(ll x) { int stackk[20]; if(x<0) { putchar('-'); x=-x; } if(!x) { putchar('0'); return; } int top=0; while(x) stackk[++top]=x%10,x/=10; while(top) putchar(stackk[top--]+'0'); } char s[maxn]; ll n,ans=inf,vis[maxn]; bool check() { for(int i=0 ;i<26 ;i++) if(!vis[i]) return 0; return 1; } int UpMing() { cin>>(s+1); n = strlen(s+1); ll l=1,r=1; while(r<=n) { int temp=s[r]-'a'; vis[temp]++; while(check()) ans=min(ans,r-l+1),vis[s[l]-'a']--,l++; r++; } out(ans); Accept; } /* */