现在有一个长度为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,保证字符串中字母均为小写字母注意,所给字符串不含引号
class Solution: def Maximumlength(self , x ): # write code here left, right = 0, 0 res = 0 counter = dict(n=0, p=0, y=0) while right < len(x): if x[right] in "npy": counter[x[right]] += 1 while counter['n'] and counter['p'] and counter['y']: if x[left] in "npy" and counter[x[left]]: counter[x[left]] -= 1 left += 1 res = max(res, right - left + 1) right += 1 return res
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; }