牛客编程巅峰赛S2第5场 - 青铜&白银&黄金 B题

https://ac.nowcoder.com/acm/contest/9556/B

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

示例1
输入
复制
"abcdefghijklmn"
返回值
复制
14
说明
因为所有子串都不同时含有n，p，y，所以最长子串的长度即为字符串x的长度14。

示例2
输入
复制
"ynp"
返回值
复制
2
说明
长度为2的字串”yn”,”np”都符合题意，不存在长度>=3的符合条件的子串。

示例3
输入
复制
"ypknnbpiyc"
返回值
复制
7
说明
“pknnbpi”为其符合条件的最长子串，长度为7。

本 caiji 一开始想到解法是 二分，即二分答案，让后从前往后 检查是否 存在 长度 为 mid 的字符串 满足 至少不含 ‘npy’ 其中一个字符的字符串，可以预处理出 0-i 之间 含有多少个'npy'，这样检查的时候就快一点

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

     int s[2000010][3];
    bool check(int mid,string &x){
        for (int i=0;i<=x.size()-1-mid+1;i++){
            int ed = i+mid-1;
            int sn = s[ed+1][0]-s[i][0];
            int sp= s[ed+1][1]-s[i][1];
            int sy=s[ed+1][2]-s[i][2];
            if (sn==0 || sp==0 || sy ==0)
                return true;
        }
        return false ;

    }
    int Maximumlength(string x) {
        // write code here


        for (int i =0;i<x.size();i++){
            for (int j=0;j<3;j++)
                s[i+1][j] = s[i][j];
            if (x[i] == 'n')
                s[i+1][0] ++;
            else if(x[i] == 'p')
                s[i+1][1]++;
            else if (x[i] == 'y')
                s[i+1][2]++;
        }
        int l =1,r=x.size();

        while (l<r){
            int mid = (l+r+1)>>1;

            if (check(mid,x)) l = mid;
            else r = mid-1;
        }
        return l;
    }
};