【Day 43 】2021-10-22 - 1456. 定长子串中元音的最大数目

[azl397985856]

1456. 定长子串中元音的最大数目

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length

前置知识

暂无

题目描述

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

示例 1：

输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。
示例 2：

输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。
示例 3：

输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。
示例 4：

输入：s = "rhythms", k = 4
输出：0
解释：字符串 s 中不含任何元音字母。
示例 5：

输入：s = "tryhard", k = 4
输出：1

提示：

1 <= s.length <= 10^5
s 由小写英文字母组成
1 <= k <= s.length

[yanglr]

思路:

方法: 滑动窗口

• 使用一个长度为 k 的窗口从 s 的左端滑向右端
• 分别计算窗口中包含的元音字母个数，最终返回最大值

那么如何计算窗口中的元音字母个数呢？

窗口每次右移1格时，会出现两个变化： 1.窗口左端去掉了一个元素 2.窗口右端加入了一个新元素

那这样我们只需要：

• 在滑动开始时记录一下窗口中的元音个数 count，之后移动窗口时判断左端丢弃的元素和右端新增的元素是不是元音字母，对应地减少或者增加 count。
• 在循环外使用一个变量maxCount, 每次循环时, 记录count 的最大值。

最后返回这个maxCount即可。

代码

实现语言: C++

class Solution {
public:
    int maxVowels(string s, int k) {
        int maxCount = 0;
        int i = 0; /* i: 滑动窗口的右端点 */
        int count = 0;        
        while (i < s.size())
        {
            if (isVow(s[i]))
                count++;

            if (i >= k && isVow(s[i - k]))
                count--;

            maxCount = max(maxCount, count);            
            i++;
        }
        return maxCount;
    }
    bool isVow(char ch)
    {
        return ch == 'a' ||
               ch == 'e' ||
               ch == 'i' ||
               ch == 'o' ||
               ch == 'u';
    }
};

复杂度分析

• 时间复杂度: O(N)，N 为字符串的长度。
• 空间复杂度: O(1)

[thinkfurther]

思路

固定长度为3的滑动窗口

代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a','e','i','o','u'}
        l = 0 
        maxNumberOfVowels = 0
        currentNumberOfVowels = 0
        for r in range(len(s)):
            if r < k:
                if s[r] in vowels:
                    maxNumberOfVowels += 1
                    currentNumberOfVowels += 1
                continue                

            if s[l] in vowels:
                currentNumberOfVowels -= 1

            if s[r] in vowels:
                currentNumberOfVowels += 1

            maxNumberOfVowels = max(maxNumberOfVowels,currentNumberOfVowels)
            l += 1

        return maxNumberOfVowels

复杂度

时间复杂度 ：O(N)

空间复杂度：O(1)

[pophy]

思路

• 固定长度滑动窗口

Java Code

class Solution {
    static Set<Character> set = new HashSet();
    static {
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
    }

    public int maxVowels(String s, int k) {
        int n = s.length();
        if (k > n) {
            k = n;
        }
        int vowelsInWindow = 0;
        for (int i = 0; i < k; i++) {
            if (set.contains(s.charAt(i))) {
                vowelsInWindow++;
            }
        }
        int max = vowelsInWindow;
        for (int i = k; i < n; i++) {
            if (set.contains(s.charAt(i - k))) {
                vowelsInWindow--;
            }
            if (set.contains(s.charAt(i))) {
                vowelsInWindow++;
            }
            max = Math.max(max, vowelsInWindow);
        }
        return max;
    }    
}

时间&空间

• 时间 O(N)
• 空间 O(1）

[jiabin123]

思路：滑动窗口暴力解法

class Solution {
    private HashSet<Character> ch = new HashSet<>(Arrays.asList('a','e','i','o','u'));
    public int maxVowels(String s, int k) {
        int num = 0;
        for(int i = 0; i <k; i++){
            if(ch.contains(s.charAt(i))){
                num ++;
            }
        }
        int window = num;
        for(int left = 0,right = k; right < s.length();right++,left ++){
            if(ch.contains(s.charAt(right))) window ++;
            if(ch.contains(s.charAt(left))) window --;
            num = Math.max(window,num);
        }
        return num;
    }

}

空间复杂度：O(1)

时间复杂度：O(N)

[zhy3213]

思路

滑动窗口，且窗口长度固定 维护一个fifo队列，使得窗口划出时不用再判断是否在原音列表中

代码

    def maxVowels(self, s: str, k: int) -> int:
        vows={'a', 'e', 'i', 'o', 'u'}
        res, tmp=0, 0
        q=collections.deque()
        for i in range(k):
            if s[i] in vows:
                tmp+=1
                q.append(True)
            else:
                q.append(False)
        res=tmp
        for r in range(k,len(s)):
            if s[r] in vows:
                tmp+=1
                q.append(True)
            else:
                q.append(False)
            if q.popleft():
                tmp-=1
            if tmp>res:
                res=tmp
        return res

[CoreJa]

思路

这个题把元音放在一个set中，然后两个指针去滑动字符串即可。每次滑动后，判断新进来的字符和退出的字符是否在元音集合中，以维护元音数量。

代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowel_set=set(['a','e','i','o','u'])
        vowel=max_vowel=0
        left,right=0,k-1
        for i in range(k):
            if s[i] in vowel_set:
                vowel+=1
        max_vowel=vowel
        for i in range(right+1,len(s)):
            if s[i] in vowel_set:
                vowel+=1
            if s[i-k] in vowel_set:
                vowel-=1
            max_vowel=max(vowel,max_vowel)
        return max_vowel

复杂度分析

时间复杂度O(n) 空间复杂度O(1)

[JiangyanLiNEU]

Sliding Window

• window length is k, we only need to check if the leftmost element and rightmost element are vowels and update the result
• Runtime = O(n)
• Space = O(1)

  JavaScript Code

  var maxVowels = function(s, k) {
  //     Initialize vowels set
  let result = 0;
  const vowels = new Set(["a",'e','i','o','u'])
  //     initialze the window
  for (let i=0;i<k;i++){
      if (vowels.has(s[i])){
          result++;
      };
  };
  //     move the window from left to right and update the result
  let left = 0;
  let right = k;
  let temp = result;
  while (right<s.length){
      if (vowels.has(s[right])){
          if (!(vowels.has(s[left]))){
              temp++;
          }
      }else{
          if (vowels.has(s[left])){
              temp--;
          };
      };
      result = result > temp ? result : temp
      right++;
      left++;
  };
  return result;
  };

[leo173701]

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        temp = []
        count = 0
        res = 0
        Vowel = {"a","e","i","o","u"}
        for i in s:
            # print("i=",i)
            if len(temp)>=k:
                if temp[0] in Vowel:
                    count-=1
                temp.pop(0)
            if i in Vowel:
                count+=1
            temp.append(i)
            # print(temp)
            res = max(res, count)
        return res 

[xinhaoyi]

1456. 定长子串中元音的最大数目

思路一

先遍历前k个字符，记录元音字母个数cnt，并初始化返回值res = cnt，这时候滑动窗口已经构建好了 继续遍历索引k开始的字符，如果索引i - k处（也就是滑动窗口外）的字符也是元音字符，cnt - 1 如果当前字符为元音字符，cnt + 1，并且更新res

代码

class Solution {
    public int maxVowels(String s, int k) {
        int cnt = 0;
        for(int i = 0; i < k; i++){
            if(isVowel(s.charAt(i))){
                cnt++;
            }
        }
        int res = cnt;
        //到这里窗口已经构建好了
        for(int i = k; i < s.length(); i++){
            if(isVowel(s.charAt(i - k))){
                cnt--;
            }
            if(isVowel(s.charAt(i))){
                cnt++;
                res = Math.max(res, cnt);
            }
        }
        return res;
    }

    private boolean isVowel(char ch) {
        //判断是否是元音
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }
}

复杂度分析

时间复杂度：O(n) 空间复杂度：O(1)

[heyqz]

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        ans = cnt = 0

        for i in range(k):
            if s[i] in vowels:
                cnt += 1
        ans = max(ans, cnt)

        for j in range(k, len(s)):
            if s[j-k] in vowels:
                cnt -= 1
            if s[j] in vowels:
                cnt += 1
            ans = max(ans, cnt)

        return ans 

time complexity: O(n) space complexity: O(1)

[biancaone]

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        if not s:
            return 0

        result = 0
        left = 0
        count = 0

        vowels = {'a', 'e', 'i', 'o', 'u'}

        for right in range(len(s)):
            if s[right] in vowels:
                count += 1

            while right - left + 1 > k:
                if s[left] in vowels:
                    count -= 1
                left += 1

            result = max(result, count)

        return result

[nonevsnull]

思路

• 拿到题的直觉解法
  • 双指针固定窗口k，然后滑动向右，检查头尾的元音情况；

AC

代码

class Solution {
    public int maxVowels(String s, int k) {
        int count = 0;
        int max = 0;
        var set = Set.of('a', 'e', 'i', 'o', 'u');

        while(count < k){
            if(set.contains(s.charAt(count++))){
                max++;
            }
        }
        int last = max;
        int right = k;
        for(int i = 0;i < s.length()-k;i++){
            int c1 = set.contains(s.charAt(i))?-1:0;
            int c2 = set.contains(s.charAt(right++))?1:0;
            last = last + c1 + c2;
            max = Math.max(max, last);
        }

        return max;
    }
}

复杂度

time: O(N) space: O(1)

[yachtcoder]

Sliding window O(n), O(1)

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        l = 0
        count = 0
        ret = 0
        for r in range(len(s)):
            if s[r] in "aeiou":
                count += 1
            while r - l + 1 > k:
                if s[l] in 'aeiou':
                    count -= 1
                l += 1
            ret = max(count ,ret)
        return ret

[zhangzz2015]

思路

• 典型应用sliding window。因为需要统计在一个窗口里面字符的个数。采用固定的滑动窗口，统计窗口中最大的元音个数。当往右滑动，最左边元音移出统计，最右边的元音加入统计。时间复杂度为O(n)，空间复杂度为O(1).

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int maxVowels(string s, int k) {

        int ret =0; 
        int count=0; 
        for(int i=0; i< k; i++)
        {
            if(isVowel(s[i]))
            {
                count++; 
                ret = max(ret, count); 
            }
        }

        for(int i=k; i<s.size(); i++)            
        {
            if(isVowel(s[i-k]))
            {
                count--;
            }
            if(isVowel(s[i]))
            {
                count++; 
                ret = max(ret, count);                 
            }
        }

        return ret;         
    }

    bool isVowel(char letter)
    {
        return  letter =='a' || letter =='e' || letter =='i' || letter =='o' || letter =='u'; 
    }
};

[florenzliu]

Explanation

• sliding window of length k
• update the current count of vowel letters by checking if the current index i and the index of i-k is vowel letter

Python

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        curr_vowel = 0
        max_vowel = 0
        vowel_set = set(["a", "e", "i", "o", "u"])
        for i in range(len(s)):
            if s[i] in vowel_set:
                curr_vowel += 1
            if i >= k-1:
                if i >= k and s[i-k] in vowel_set:
                    curr_vowel -= 1
                max_vowel = max(max_vowel, curr_vowel)
        return max_vowel

Complexity:

• Time Complexity: O(N)
• Space Complexity: O(1)

[ZacheryCao]

Idea:

Sliding window with fixed length. Initialize the left ("l") and right ("r") side of the sliding window at 0. First increase "r" to k-1 and check how many vowel letters it has. Let's say it's cnt. Second increase "l" and "r" by 1. If the most left letter we remove from current window is a vowel letter, minus cnt with 1. If the new element we added from right side is a vowl letter, we increase cnt by one. Everytime we update the "l" and "r", we find the max value between previous ans and cnt.

Code:

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ans, cur = 0, 0
        l , r = 0, 0
        if len(s) < k or not s:
            return ans
        vowel = {'a', 'e', 'i', 'o', 'u'}
        while r - l + 1 < k:
            if s[r] in vowel:
                cur += 1
            r += 1
        if s[r] in vowel:
            cur += 1
        for _ in range(r, len(s)):
            ans = max(cur, ans)
            if s[l] in vowel:
                cur -= 1
            l += 1
            r += 1
            if r < len(s) and s[r] in vowel:
                cur += 1
        return max(ans, cur)

Complexity:

Time: O(N). N is the length of the string. We scan through the string only once. Space: O(1). No extra space needed. The set for vowel letters is O(1)

[Menglin-l]

连续子串，想到滑窗

---

代码部分：

class Solution {
    public int maxVowels(String s, int k) {

        int ans = 0;
        for (int i = 0; i < k; i ++) {
            if (isVowel(s.charAt(i))) ans ++;
        }

        int count = ans;
        for (int j = k; j < s.length(); j ++) {
            if (isVowel(s.charAt(j - k))) count --;
            if (isVowel(s.charAt(j))) count ++;

            ans = Math.max(count, ans);
        }

        return ans;
    }

    public boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

---

复杂度：

Time: O(N)，N为s长度

Space: O(1)

[erik7777777]

class Solution {
    public int maxVowels(String s, int k) {
        int start = 0;
        int end = 0;
        int count = 0;       
        for (; end < k; end++) {
            if (checkVowel(s.charAt(end))) count++;
        }
        int res = count;
        while (end < s.length()) {
            if (checkVowel(s.charAt(end++))) {
                count++;
            }
            if (checkVowel(s.charAt(start++))) {
                count--;
            }
            res = Math.max(res, count);
        }
        return res;
    }

    private boolean checkVowel(char c) {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
            return true;
        }
        return false;
    }
}

sliding window Time : O(n), Space : O(1)

[st2yang]

思路

• 滑动窗口

代码

• python

  class Solution:
  def maxVowels(self, s: str, k: int) -> int:
      def is_vowel(c):
          return c in "aeiou"
  
      res = sum(1 for i in range(k) if is_vowel(s[i]))
      curr = res
      for i in range(k, len(s)):
          curr = curr + is_vowel(s[i]) - is_vowel(s[i-k])
          res = max(res, curr)
  
      return res

复杂度

• 时间: O(n)
• 空间: O(1)

[zjsuper]

Idea: sliding windows Time O(N), N =len(s)

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        start = 0
        end = k-1
        strings = s[start:end+1]
        #print(strings)
        max_num = 0
        for ss in strings:
            if ss in "aeiou":
                max_num += 1
        ans = max_num
        for i in range(k,len(s)):
            if s[i] in "aeiou" and strings[0] not in "aeiou":
                max_num +=1
                ans = max(ans, max_num)
            elif s[i] not in "aeiou" and strings[0] in "aeiou":
                max_num -=1
            start += 1
            end +=1
            strings = s[start:end+1]
            #print(strings)
        return ans

[wangzehan123]

题目地址(1456. 定长子串中元音的最大数目)

https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/

题目描述

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

 

示例 1：

输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。

示例 2：

输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。

示例 3：

输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。

示例 4：

输入：s = "rhythms", k = 4
输出：0
解释：字符串 s 中不含任何元音字母。

示例 5：

输入：s = "tryhard", k = 4
输出：1

 

提示：

1 <= s.length <= 10^5
s 由小写英文字母组成
1 <= k <= s.length

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
    public int maxVowels(String s, int k) {
        HashSet<Character> set = new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        int len = s.length();
        int count = 0, res = 0;
        for (int i = 0; i < k; i++) {
            if (set.contains(s.charAt(i)))
            count++;
        }
        res = count;
        for (int i = k; i < len; i++) {
            if (set.contains(s.charAt(i-k)))
                count--;
            if (set.contains(s.charAt(i)))
                count++;
            res = Math.max(res, count);
        }
        return res;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[xieyj17]

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set(['a','e','i','o','u'])
        left = 0
        right = left + k
        n = len(s)
        res = sum([i in vowels for i in s[left:right]])
        nr = res
        while right < n:
            nr = nr + (s[right] in vowels) - (s[left] in vowels)
            res = max(nr,res)
            left += 1
            right += 1

        return res

In each step # of vowels in the rolling window +1 if the next char is a vowel and -1 if the first char is a vowel

Time: O(N)

Space: O(1)

[yingliucreates]

link:

https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/

代码 Javascript

const maxVowels = function(s, k) {
    const vowels = new Set(["a", "e", "i", "o", "u"]);

    let maxCount = 0;
    let currCount = 0;
    let l = 0;
    let i = 0;

    while (i < k) {
        if (vowels.has(s[i++])) maxCount = Math.max(maxCount, ++currCount);
    }

    while (i < s.length) {
        if (vowels.has(s[l++])) currCount--;
        if (vowels.has(s[i++])) maxCount = Math.max(maxCount, ++currCount);
    }

    return maxCount;
};

复杂度分析

time O(n) space O(1)

[joeytor]

思路

使用滑动窗口的思路

每次滑动一次窗口时, 如果新的 index 是 vowel, count += 1, 如果原来的 第一个 index 是 vowel, count -= 1

每一次更新窗口后 res = max(res, count), 更新 res 的值

class Solution:
    def maxVowels(self, s: str, k: int) -> int:

        vowel_set = {'a','e','i','o','u'}

        res = 0
        count = 0
        for i, c in enumerate(s):
            count += c in vowel_set
            if i > k-1:
                j = i - k
                count -= s[j] in vowel_set

            if count > res:
                res = count

        return res

复杂度

时间复杂度: O(n) 遍历字符串的复杂度

空间复杂度: O(1)

[Daniel-Zheng]

思路

滑动窗口。

代码(C++)

class Solution {
public:
    int maxVowels(string s, int k) {
        unordered_set<char> hashSetVowels = {'a', 'e', 'i', 'o', 'u'};
        int count = 0, res = 0;
        for (int i = 0; i < s.size(); i++) {
            if (i >= k) count -= hashSetVowels.count(s[i - k]);
            count += hashSetVowels.count(s[i]);
            res = max(res, count);
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[siyuelee]

滑动窗口，维持一个长度为k的窗口

class Solution(object):
    def maxVowels(self, s, k):
        l = 0
        r = l + k
        res = 0
        char = set(['a','e','i','o','u'])
        for i in range(k):
            res += s[i] in char
        if res == k: return k
        temp = res
        while r < len(s):
            temp = temp + (s[r] in char) - (s[l] in char)
            res = max(temp, res)
            l += 1
            r += 1
        return res

T: n S: 1

[jiahui-z]

思路: Maintain a sliding window with size of k, check the first window in the array to get the number of vowels, then slide the window all the way to the end of the array. If the next element is a vowel, then plus one for the number of vowels; if the past element is a vowel, then minus one for the number of vowels.

class Solution {
    public int maxVowels(String s, int k) {
        Set<Character> set = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
        int result = 0, cur = 0;
        for (int i = 0; i < k; i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                cur++;
                result = cur;
            }
        }

        for (int j = k; j < s.length(); j++) {
            if (set.contains(s.charAt(j))) {
                cur++;
            }
            if (set.contains(s.charAt(j-k))) {
                cur--;
            }
            result = Math.max(result, cur);
        }

        return result;
    }
}

Time complexity: O(n)

Space complexity: O(1)

[Francis-xsc]

思路

滑动窗口

代码

class Solution {
public:
    bool isVowels(char c)
    {
        return c=='a'||c=='e'||c=='i'||c=='o'||c=='u';
    }
    int maxVowels(string s, int k) {
        int l=0,r=0,cur=0,len=s.size();
        for(;r<k;r++)
        {
            if(isVowels(s[r]))
                cur++;
        }
        --r;
        int res=cur;
        while(r<len)
        {
            if(isVowels(s[l]))
                cur--;
            ++l;
            ++r;
            if(isVowels(s[r]))
                cur++;
            res=res>cur?res:cur;
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[yan0327]

思路： 先设置一个判断是否为元音字符的函数，通过这个函数来实现对窗口内元音的计数 该题是一道固定窗口长度的题目，因此可以先移动k步，计算单窗口内元音数，然后再首尾同时向右移动，实现固定窗口，每次对移除的字符和添加的字符进行判断，从而管理窗口内的元音数目

func maxVowels(s string, k int) int {
    out := 0
    for i:=0;i<k;i++{
        if isValid(s[i]){
            out++
        }
    }
    cur := out
    for i:=k;i<len(s);i++{
        if isValid(s[i-k]){
            cur--
        }
        if isValid(s[i]){
            cur++
        }
        if cur > out{
            out = cur
        }
    }
    return out
}

func isValid (c byte) bool{
    if c == 'a'|| c == 'e'|| c == 'i'|| c == 'o'|| c == 'u'{
        return true
    }else{
        return false
    }
}

时间复杂度：O（n） 空间复杂度：O（1）

[zhangyalei1026]

思路

固定长度的滑动窗口，将第一个窗口中的vowel个数保存， 然后开始滑动窗口，去除窗口最左元素，增加窗口最右元素，如果需要去除的最左元素是vowel，那么在保存的第一个窗口vowel数上减去一，如果最右是vowel，则加一，不断更新结果最后返回最大的vowel数目

代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowel = {"a", "e", "i", "o", "u"}
        ans = 0
        for i in range(k):
            if s[i] in vowel:
                ans += 1
        temp = ans
        for right in range(k, len(s)):

            left = right - k
            if s[left] in vowel:
                temp -= 1
            if s[right] in vowel:
                temp += 1
            ans = max(temp, ans)
        return ans

复杂度分析

时间复杂度：O(n) 空间复杂度：O(1)

[mannnn6]

代码

class Solution {
    public int maxVowels(String s, int k) {
        int n = s.length();
        int vowel_count = 0;
        for (int i = 0; i < k; ++i) {
            vowel_count += isVowel(s.charAt(i));
        }
        int ans = vowel_count;
        for (int i = k; i < n; ++i) {
            vowel_count += isVowel(s.charAt(i)) - isVowel(s.charAt(i - k));
            ans = Math.max(ans, vowel_count);
        }
        return ans;
    }

    public int isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
    }
}

复杂度

时间复杂度：O（n） 空间复杂度：O（1）

[tongxw]

思路

固定长度滑动窗口

代码

class Solution {
    public int maxVowels(String s, int k) {
        Set<Character> set = new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');

        int count = 0;
        for (int i=0; i<k; i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                count++;
            }
        }

        int ans = count;
        for (int i=k; i<s.length(); i++) {
            if (set.contains(s.charAt(i - k))) {
                count--;
            }
            if (set.contains(s.charAt(i))) {
                count++;
            }

            ans = Math.max(ans, count);
        }

        return ans;
    }
}

• TC: O(n)
• SC: O(1)

[freesan44]

思路

通过滑动窗口遍历来算出最大值

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        coreDic = dict()
        coreDic = {"a":1,"e":1,"i":1,"o":1,"u":1}
        res,temp = 0,0
        #先形成k那样的滑动窗口
        for i in s[:k]:
            if i in coreDic:
                temp += 1
        if len(s) == k : return temp
        res = temp
        #开始滑动窗口，把旧的-1，新的+1
        for index,val in enumerate(s[k:]):
            if s[index] in coreDic:
                temp -= 1
            if val in coreDic:
                temp += 1
            res = max(temp,res)
        return res

if __name__ == '__main__':
    s = "abciiidef"
    k = 3
    result = Solution().maxVowels(s,k)
    print(result)

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

[xj-yan]

class Solution {
    public int maxVowels(String s, int k) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));

        int count = 0;
        for (int i = 0; i < k; i++){
            char c = s.charAt(i);
            if (vowels.contains(c)) count++;
        }
        int maxNum = count;
        for (int i = k; i < s.length(); i++){
            count += (vowels.contains(s.charAt(i)) ? 1 : 0) - (vowels.contains(s.charAt(i - k)) ? 1 : 0);
            maxNum = Math.max(count, maxNum);
        }
        return maxNum;
    }
}

Time Complexity: O(n), Space Complexity: O(1)

[RocJeMaintiendrai]

题目

https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/

思路

固定滑动窗口，每次向右移动一位，加上右边的减掉左边的如果是元音的话，取最大值即可。

代码

class Solution {
    public int maxVowels(String s, int k) {
        int n = s.length();
        int vowel_count = 0;
        for(int i = 0; i < k; i++) {
            vowel_count += isVowel(s.charAt(i));
        }
        int res = vowel_count;
        for(int i = k; i < n; i++) {
            vowel_count += isVowel(s.charAt(i)) - isVowel(s.charAt(i - k));
            res = Math.max(res, vowel_count);
        }
        return res;
    }

    public int isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
    }

}

复杂度分析

时间复杂度

O(n)

空间复杂度

O(1)

[laofuWF]

# sliding window
# time: O(N)
# space: O(1)

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = "aeiou"
        count = 0

        for i in range(k):
            if s[i] in vowels:
                count += 1

        res = count

        for i in range(k, len(s)):
            if s[i - k] in vowels:
                count -= 1
            if s[i] in vowels:
                count += 1

            res = max(res, count)

        return res

[zol013]

维持一个变量 num_of_vowel记录当前滑动窗口中元音个数，创建左窗口i = 0，右窗口j遍历0到n - 1，nums[j]是元音时 num_of_vowel + 1，然后检查窗口大小是否小于等于k，如果大于k, 先检查左窗口的字母是否为元音，是的话num_of_vowel -1 并移动左窗口 i += 1， 最后更新答案ans = max(ans, num_of_vowel) Python 3 code

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ans = 0
        num_of_vowel = 0
        i = 0
        for j in range(len(s)):
            if s[j] in 'aeiou':
                num_of_vowel += 1
            if j - i + 1 > k:
                if s[i] in 'aeiou':
                    num_of_vowel -= 1
                i += 1
            ans = max(ans, num_of_vowel)
        return ans

Time Complexity: O(n) Space Complexity: O(1)

[SunnyYuJF]

思路

sliding windows

代码 Python

def maxVowels(self, s: str, k: int) -> int:
        vowels = ["a","e","i","o","u"]
        res=0
        for j in range(k):
            if s[:k][j] in vowels:
                res+=1
        i = 1
        cnt = res
        while i<=len(s)-k:

            if s[i-1] in vowels:
                cnt-=1
            if s[i+k-1] in vowels:
                cnt+=1

            i+=1
            res = max(res,cnt)

        return res

复杂度分析

时间复杂度： O(N)
空间复杂度： O(1)

[user1689]

题目

https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/

思路

imitation

python3

class Solution:
    def maxVowels(self, s: str, k: int) -> int:

        # time n
        # space n
        Vowels = {'a','e','i','o','u'}
        # queue = collections.deque()

        # 初始化窗口
        i = 0
        cnt = 0
        for j in range(k):
            if s[j] in Vowels:
                cnt += 1

        # 菜鸡滑动窗口
        n = len(s)
        maxCnt = cnt
        while j < n - 1:
            if s[i] in Vowels:
                cnt -= 1
            if s[j+1] in Vowels:
                cnt += 1
            i += 1
            j += 1  
            maxCnt = max(maxCnt, cnt)
        return maxCnt

复杂度分析

• time n
• space n

相关题目

1. https://leetcode-cn.com/problems/sliding-window-maximum/

[pan-qin]

idea:

sliding window. when the window size j-i+1 <=k, check if the char at index j is vowel and advance j; when the window size >k , check if the char at index i is vowel and advance i.

Complexity:

Time: O(n) Space: O(1)

class Solution {
    public int maxVowels(String s, int k) {
        int max=0, count=0;
        int i=0, j=0, len=s.length();
        while(j<len && i<len) {
            while(j-i+1<=k) {
                if(isVowel(s.charAt(j))) {
                    count++;
                }
                j++;
            }
            max=Math.max(max,count);
            if(j-i+1>k) {
                if(isVowel(s.charAt(i)))
                    count--;
                i++;
            }
        }
        return max;
    }
    public boolean isVowel(char c) {
        if(c=='a' || c=='e'|| c=='i' || c=='o'|| c=='u')
            return true;
        return false;
    }
}

[Moin-Jer]

思路

---

滑动窗口

代码

---

class Solution {
    public int maxVowels(String s, int k) {
        char[] ch = s.toCharArray();
        int len = ch.length, l = 0, r = 0, ans = 0, tmp = 0;
        while (r < k) {
            if (ch[r] == 'a' || ch[r] == 'e' || ch[r] == 'i' || ch[r] == 'o' || ch[r] == 'u') {
                ++tmp;
            }
            ++r;
        }
        ans = Math.max(ans, tmp);
        while (r < len) {
            if (ch[l] == 'a' || ch[l] == 'e' || ch[l] == 'i' || ch[l] == 'o' || ch[l] == 'u') {
                --tmp;
            }
            ++l;
            if (ch[r] == 'a' || ch[r] == 'e' || ch[r] == 'i' || ch[r] == 'o' || ch[r] == 'u') {
                ++tmp;
            }
            ++r;
            ans = Math.max(ans, tmp);
        }
        return ans;
    }
}

复杂度分析

---

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[ghost]

题目

1456. Maximum Number of Vowels in a Substring of Given Length

思路

Sliding window

代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        res = 0

        for i in range(k):
            res += s[i] in vowels

        curr = res

        for j in range(k, len(s)):

            if s[j-k] in vowels:
                curr-=1
            if s[j] in vowels:
                curr+=1
            res = max(res, curr)

        return res

复杂度

Space: O(1) Time: O(S)

[shamworld]

思路

滑动窗口

代码

var maxVowels = function(s, k) {
    let obj = new Set(['a','e','i','o','u']);
    let count = 0,right=0,left=0;
    let len = s.length;
    //第一次k长度里面有多少元音
    while(right<k){
        obj.has(s[right++]) && count++;
    }
    let res = count;
    // 后面就是right向右遇到就累加，而left向右遇到就递减
    while(right<len){
        obj.has(s[right++]) && count++;
        obj.has(s[left++]) && count--;
        res = Math.max(res,count);
    }
    return res;
};

[cicihou]

import collections

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ''' sliding window
        time O(n)
        space O(k)
        '''
        vowels = 'aeiou'
        res = 0
        count = 0
        window = collections.deque()
        for i in range(len(s)):
            window.append(s[i])
            if s[i] in vowels:
                count += 1
            if len(window) > k:
                tmp = window.popleft()
                if tmp in vowels:
                    count -= 1
            res = max(res, count)
            # 这里可以再加一个小优化，当 res 达到最大值，提前进行返回
            # if res == k:
            #     return res
        return res

[zhiyuanpeng]

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a','e','i','o','u'}
        l = 0 
        maxNumberOfVowels = 0
        currentNumberOfVowels = 0
        for r in range(len(s)):
            if r < k:
                if s[r] in vowels:
                    maxNumberOfVowels += 1
                    currentNumberOfVowels += 1
                continue                

            if s[l] in vowels:
                currentNumberOfVowels -= 1

            if s[r] in vowels:
                currentNumberOfVowels += 1

            maxNumberOfVowels = max(maxNumberOfVowels,currentNumberOfVowels)
            l += 1

        return maxNumberOfVowels

[wangyifan2018]

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        n, res, temp = len(s), 0, 0
        vowels = set(['a','e','i', 'o', 'u'])
        for i in range(k):
            res += s[i] in vowels
        if res == k: return k
        temp = res
        for i in range(k, n):
            temp += (s[i] in vowels) - (s[i - k] in vowels)
            res = max(temp, res)
            if res == k: return k
        return res

[Jinjin680]

思路

• 定长滑动窗口

C++代码

class Solution {
public:
    bool isVowel(char c){
        return c == 'a'|| c == 'e'|| c == 'i'|| c == 'o'|| c == 'u';
    }
    int maxVowels(string s, int k) {
        int temp = 0, res = 0;
        for(int i = 0; i < s.size(); i++){
            if(isVowel(s[i])) temp++;
            if(i >= k && isVowel(s[i - k])) temp--;
            res = max(res, temp);
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[ZJP1483469269]

题目地址(1456. 定长子串中元音的最大数目)

https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/

题目描述

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

 

示例 1：

输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。

示例 2：

输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。

示例 3：

输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。

示例 4：

输入：s = "rhythms", k = 4
输出：0
解释：字符串 s 中不含任何元音字母。

示例 5：

输入：s = "tryhard", k = 4
输出：1

 

提示：

1 <= s.length <= 10^5
s 由小写英文字母组成
1 <= k <= s.length

前置知识

公司

• 暂无

思路

滑动窗口

关键点

• 用滑窗降低时间复杂度

代码

• 语言支持：Java

Java Code:

class Solution {
    public int maxVowels(String s, int k) {
        char c;
        int max = 0;
        int ans = 0;
        for(int i = 0;i < k ;i++){
            c = s.charAt(i);
            if(c == 'a' | c == 'e' | c == 'i' | c == 'o' | c == 'u'){
                ans++;
            }
        }
        max = Math.max(max,ans);
        int l = 0, r = k;
        while(r < s.length()){
            c = s.charAt(l);
            if(c == 'a' | c == 'e' | c == 'i' | c == 'o' | c == 'u'){
                ans--;
            }
            l++;
            c = s.charAt(r);
            if(c == 'a' | c == 'e' | c == 'i' | c == 'o' | c == 'u'){
                ans++;
            }
            r++;
            max = Math.max(max,ans);
        }
        return max;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

[flagyk5]

'''
时间 n
空间 1
'''
class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ds = ['a','e','i','o','u']
        le, rt = 0, k
        ans = 0
        if len(s) < k: return none
        for i in range(0,k):
            if s[i] in ds: ans += 1
        if ans == k: return k
        newans = ans
        while rt <= len(s)-1:
            if s[rt] in ds: newans = newans+1
            if s[le] in ds: newans = newans-1
            ans = max(ans, newans)
            if ans == k: return k                    
            le += 1
            rt += 1            
        return ans

[laurallalala]

代码

class Solution(object):
    def maxVowels(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        ct = [0]*26
        for i in range(k):
            if s[i] in "aeiou":
                ct[ord(s[i])-ord("a")] += 1
        res = max(0, sum(ct))
        for i in range(k, len(s)):
            j = i-k
            if s[j] in "aeiou":
                ct[ord(s[j])-ord("a")] -= 1
            if s[i] in "aeiou":
                ct[ord(s[i])-ord("a")] += 1
            res = max(res, sum(ct))
        return res

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)