算法入门——合法字串(双指针)

枚举 · 例14-最短合法子串

https://ac.nowcoder.com/acm/contest/20960/1015

题意

  • 在字符串S中找一个最短字串,使其包含26个字母

思路

  • 暴力枚举会T
  • 双指针:从头开始扫,更新右界直到扫全,然后更新左界直到缺字母,重复上述过程遍历整个串

AC代码

#include<bits/stdc++.h>
using namespace std;
int vis[26];
int main(){
    string s;
    cin>>s;
    int slen=s.size();
    int rst=1e7,cnt=0;
    if(slen<27)cout<<-1<<endl;
    else{
        for(int l=0,r=0;l<slen;l++){
            while(r<slen&&cnt<26)
            {
                if(vis[s[r]-'a']==0)cnt++;
                vis[s[r]-'a']++;
                r++;
            }
            if(cnt==26) rst=min(rst,r-l);
            vis[s[l]-'a']--;
            if(vis[s[l]-'a']==0)cnt--;          
        }
        printf("%d\n",rst);
    }

}

双指针的一些注意事项:

  • 对于右界的更新问题:由于一般情况下只要进入了更新右界的循环就会给右边界加一,但是在满足条件时我们希望右边界不动,所以在更新右边界的循环里往往带着判定条件也就是本题的cnt<26if(cnt==26) rst=min(rst,r-l)

  • 这种对边界预处理的体现在丢手绢一题中体现更为明显

  •   while(r<=n&&(sum+dis[r])*2<=ads)
    
全部评论

相关推荐

能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
07-07 12:47
门头沟学院 Java
码农索隆:竟然还真有卡体检报告的
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务