现在有一个长度为m的只包含小写字母‘a’-‘z’的字符串x,求字符串中不同时含有n,p,y三个字母的最长字串的长度是多少?。(对于字符串”abc”来说,”c”,”ab”都是原串的子串,但”ac”不是原串子串)
"abcdefghijklmn"
14
因为所有子串都不同时含有n,p,y,所以最长子串的长度即为字符串x的长度14。
"ynp"
2
长度为2的字串”yn”,”np”都符合题意,不存在长度>=3的符合条件的子串。
"ypknnbpiyc"
7
“pknnbpi”为其符合条件的最长子串,长度为7。
对于
的数据
对于
的数据
函数共有一个参数,即题目描述中的字符串x,保证字符串中字母均为小写字母注意,所给字符串不含引号
public class Solution {
public int Maximumlength (String x) {
// write code here
int max = 0;
int left = 0,right = 0;
int n = 0,p = 0,y = 0;
while(right < x.length()){
if(x.charAt(right) == 'n') n ++;
else if(x.charAt(right) == 'p') p ++;
else if(x.charAt(right) == 'y') y ++;
if(n >= 1 && p >= 1 && y >= 1){
if(x.charAt(left) == 'n') n --;
else if(x.charAt(left) == 'p') p --;
else if(x.charAt(left) == 'y') y --;
left ++;
}
right ++;
max = Math.max(max,right - left);
}
return max;
}
} public static int npy(String str) {
int max = 0;
//用来存放途经的n、p、y,因为集合不能重复,所以经过重复的n、p、y也只能算一个
Set<Character> set = new HashSet<>();
//转换成字符数组
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
int count = 0;
//最大可能长度都不可能大于最大长度了就没必要再进行测试下去了
if (chars.length-i<=max){
break;
}
for (int j = i; j < chars.length; j++) {
//只要不是n、p、y直接加1
if (chars[j] != 'n' && chars[j] != 'p' && chars[j] != 'y') {
count++;
} else {
//是n、p、y其中一个直接加入set,然后看是不是已经把n、p、y全部途经了,没有继续加以
set.add(chars[j]);
if (set.size() == 3) {
break;
} else {
count++;
}
}
}
if (count > max) {
max = count;
}
//清空集合数据,重新计算途经的n、p、y个数
set.clear();
}
return max;
}