牛客编程巅峰赛S2第5场 - 青铜&白银&黄金 怕pny的牛牛 (寻找最长的满足条件的子串)

题目链接:https://ac.nowcoder.com/acm/contest/9556/B

题目描述:
牛牛非常怕他的女朋友,怕到了走火入魔的程度,以至于每当他看到一个字符串同时含有n,p,y三个字母他都害怕的不行。现在有一个长度为m的只包含小写字母‘a’-‘z’的字符串x,牛牛想知道能令他不害怕的最长子串的长度是多少。(对于字符串”abc”来说,”c”,”ab”都是原串的子串,但”ac”不是原串子串

输入:

"abcdefghijklmn"

输出:

14

说明:因为所有子串都不同时含有n,p,y,所以最长子串的长度即为字符串x的长度14。
输入:

"ynp"

输出:

2

说明:长度为2的字串”yn”,”np”都符合题意,不存在长度>=3的符合条件的子串。
输入:

"ypknnbpiyc"

输出:

7

说明:“pknnbpi”为其符合条件的最长子串,长度为7

备注:

对于40%的数据 1 ≤ m ≤ 100 1≤m≤100 1≤m≤100

对于100%的数据 1 ≤ m ≤ 1   000   000 1≤m≤1 000 000 1≤m≤1 000 000
函数共有一个参数,即题目描述中的字符串x,保证字符串中字母均为小写字母
注意,所给字符串不含引号

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 返回符合题意的最长的子串长度
     * @param x string字符串 
     * @return int整型
     */
    int Maximumlength(string x) {
        // write code here
    }
};

分析:
for循环枚举所有子串的终止位置,pos=0为起始位置。
对于一个串出现’n’,‘p’,'y’三个字母出现的次数都大于等于1时,我们需要改变起始位置,即pos++。
对于每一种情况更新最大长度。

代码:

        int nnum=0,pnum=0,ynum=0;
        int mx=0,pos=0;
        ////n n n p p a y p n n p n y
        for(int i=0;i<x.size();i++)///for循环+pos=0相当于遍历所有的子串
        {
            if(x[i]=='n')
                nnum++;
            if(x[i]=='p')
                pnum++;
            if(x[i]=='y')
                ynum++;
            if(nnum>=1&&pnum>=1&&ynum>=1)
            {
                if(x[pos]=='n')
                    nnum--;
                if(x[pos]=='p')
                    pnum--;
                if(x[pos]=='y')
                    ynum--;
                pos++;
            }
            mx=max(mx,i-pos+1);
        }
上一篇:监测 Linux 上失败的登录尝试方法分享


下一篇:计算与编程思维-Python实践【Python Crash Course】