题目链接: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);
}