【Day 43 】2022-01-23 - 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

[yan0327]

思路： 双指针+固定窗口

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++
        }
        out = max(out,cur)
    }
    return out
}
func isValid(x byte) bool{
    if x=='a'||x=='o'||x=='e'||x=='i'||x=='u'{
        return true
    }
        return false
}
func max(a,b int) int{
    if a > b{
        return a
    }
        return b
}

时间复杂度O（N） 空间复杂度O（1）

[yetfan]

思路 滑动窗口设为k个字符，检测第一个和下一个要进入的字母是元辅

代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        num = 0
        for i in s[:k]:
            if i in "aeiou":
                num += 1
        maxnum = num

        for l in range(len(s)-k):
            if s[l] in "aeiou":
                num -= 1
            if s[l+k] in "aeiou":
                num += 1
                maxnum = max(maxnum, num)  # 加一个缩进，只有变大才需要计算，可以有效减少时间
        return maxnum

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

[charlestang]

思路

双指针，圈住一个窗口，统计窗口里的原因数量。

代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        l = 0
        r = 0
        v = 0
        ans = 0
        n = len(s)
        while r < n:
            if s[r] in 'aeiou':
                v += 1
            if r - l + 1 > k:
                if s[l] in 'aeiou':
                    v -= 1
                l += 1
            r += 1
            ans = max(ans, v)    
        return ans

时间复杂度 O(n)

空间复杂度： O(1)

[Brent-Liu]

class Solution { public: bool isVowel(char ch) { return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'; }

int maxVowels(string s, int k) {
    int n = s.size();
    int vowel_count = 0;
    for (int i = 0; i < k; ++i) {
        vowel_count += isVowel(s[i]);
    }
    int ans = vowel_count;
    for (int i = k; i < n; ++i) {
        vowel_count += isVowel(s[i]) - isVowel(s[i - k]);
        ans = max(ans, vowel_count);
    }
    return ans;
}

};

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/solution/ding-chang-zi-chuan-zhong-yuan-yin-de-zu-4ka7/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[zjsuper]

class Solution: def maxVowels(self, s: str, k: int) -> int: if len(s)<=k: c = 0 for i in s: if i in 'aeiou': c+=1 return c maxv = 0 maxvv = 0 for i in s[0:k]: if i in 'aeiou': maxv +=1 maxvv = max(maxvv,maxv) for j in range(k,len(s)): if s[j] in 'aeiou' and s[j-k] not in 'aeiou': maxv +=1 maxvv = max(maxvv,maxv) elif s[j] in 'aeiou' and s[j-k] in 'aeiou': pass elif s[j] not in 'aeiou' and s[j-k] not in 'aeiou': pass elif s[j] not in 'aeiou' and s[j-k] in 'aeiou': maxv -= 1 return maxvv

[zhy3213]

思路

滑动窗口

代码

    def maxVowels(self, s: str, k: int) -> int:
        vowels={'a','e','i','o','u'}
        res=0
        cur=0
        for i in range(k):
            if s[i] in vowels:
                cur+=1
        res=cur
        for i in range(k,len(s)):
            if s[i-k] in vowels:
                cur-=1
            if s[i] in vowels:
                cur+=1
                if cur > res:
                    res=cur
        return res

[zwmanman]

class Solution(object): def maxVowels(self, s, k): """ :type s: str :type k: int :rtype: int """ res = 0 curr = 0

    l = 0
    r = 0

    while r < len(s):
        c = s[r]

        if c in 'aeiou':
            curr += 1

        while r - l + 1 > k:
            p = s[l]
            l += 1

            if p in 'aeiou':
                curr -= 1

        r += 1
        res = max(res, curr)

    return res

[zhangzz2015]

思路

• 使用固定大小的sliding window方法。记录子串的vowel的大小，找到最大的返回，时间复杂度为O(n)，空间为O(1)。

关键点

代码

• 语言支持：C++

C++ Code:

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

        return ret;                     
    }
};

[Frederickfan]

    public int maxVowels(String s, int k) {
        int count = 0;
        int result = 0;
        for (int i = 0; i < k; i++) {
            count += ("aeiou".indexOf(s.charAt(i)) != -1) ? 1 : 0;
        }
        result = count;
        int i = k;
        while (i < s.length()) {
            count -= ("aeiou".indexOf(s.charAt(i-k)) != -1) ? 1 : 0;
            count += ("aeiou".indexOf(s.charAt(i)) != -1) ? 1 : 0;
            result = Math.max(result, count);
            i++;
        }
        return result;
    }

[falconruo]

思路

1. 滑动窗口

复杂度

• 时间复杂度: O(N), N为字符串s长度
• 空间复杂度: O(1), 辅助set固定长度（5)

代码(C++)

class Solution {
public:
    int maxVowels(string s, int k) {
        set<char> dict = {'a', 'e', 'i', 'o', 'u'};
        int l = 0, len = 0;

        int res = 0;

        for (int i = 0; i < s.length(); i++) {
            while (i - l + 1 > k) {
                if (dict.count(s[l]))
                    len--;
                l++;
            }

            if (i - l + 1 <= k && dict.count(s[i]))
                len++;
            res = max(res, len);
        }

        return res;
    }
};

[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

[CoreJa]

思路

• 滑动窗口：优化小tips：滑动时，只在cur增加时判断是否为最大值，以减少判断次数

代码

class Solution:
    # 滑动窗口
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        cur = 0
        for j in range(k):
            if s[j] in vowels:
                cur += 1
        ans = cur
        for j in range(k, len(s)):
            if s[j - k] in vowels:
                cur -= 1
            if s[j] in vowels:
                cur += 1
                # 只在cur增加时判断，减少判断次数
                if cur > ans:
                    ans = cur
        return ans

[feifan-bai]

思路

1. 滑动窗口
2. 构造一个元音数组的hashmap, 查询是否存在元音

代码

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

复杂度分析

• 时间复杂度：O(n), n = len(s)
• 空间复杂度：O(1)

[ZacheryCao]

Idea

Sliding window

Code

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

Complexity:

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

[youzhaing]

思路

滑动窗口

代码

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

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

[Yachen-Guo]

思路

sliding window，滑动窗口的过程中，减去前一个的元音数，加上后一个的元音数，维护这个窗口并更新max

代码

class Solution {
    public int maxVowels(String s, int k) {
        int l = 0, r = 0;
        int len = s.length();
        // window setup
        int res = 0;
        char[] words = s.toCharArray();
        while(r < k){
            res += isVowel(words[r]);
            r++;
        }
        r--;
        // sliding
        int curr = res;
        while(r < len - 1){
            curr = curr - isVowel(words[l++]) + isVowel(words[++r]);
            res = Math.max(res,curr);
        }
        return res;
    }

    private int isVowel(char test){
        if(test == 'a' || test == 'e' || test == 'i' || test == 'o' || test == 'u') return 1;
        else return 0;
    }
}

复杂度

O(N)

[Yrtryannn]

class Solution {
    public int maxVowels(String s, int k) {
        int maxCount = 0;
        for (int i = 0; i < k; i++) {
            maxCount += isVowel(s.charAt(i));
        }
        int curCount = maxCount;
        for (int i = k; i < s.length(); i++) {
            curCount += isVowel(s.charAt(i)) - isVowel(s.charAt(i - k));
            maxCount = Math.max(maxCount, curCount);
        }
        return maxCount;
    }
    public int isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
    }
}

[hdyhdy]

思路： 滑动窗口

func maxVowels(s string, k int) int {
    ans := 0 
    if len(s) <  1 {
        return ans 
    }
    for i := 0 ; i < k ; i ++ {
        if judge(s[i]){
            ans ++ 
        }
    }
    tem1 := ans 
    for i := k; i < len(s); i ++ {
        if judge(s[i - k]){
            tem1 --
        }
        if judge(s[i]){
            tem1 ++ 
        }
        ans = max(tem1,ans)
    }
    return ans 
}

func judge(que byte) bool {
    if que == 'a'||que == 'e'||que == 'i'||que == 'o'||que == 'u'{
        return true
    }
    return false 
}

func max(i,j int) int {
    if i > j {
        return i
    }else {
        return j
    }
}

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

[moirobinzhang]

Code:

public class Solution { public int MaxVowels(string s, int k) { if (string.IsNullOrEmpty(s) || s.Length < k) return 0;

    HashSet<char> vowSet = new HashSet<char>();
    vowSet.Add('a');
    vowSet.Add('e');
    vowSet.Add('i');
    vowSet.Add('o');
    vowSet.Add('u');

    int resultVowels = 0;  
    for (int i = 0; i < k; i++)
    {
        if (vowSet.Contains(s[i]))
            resultVowels++;
    }

    int currentVowels = resultVowels;

    for (int i = k; i <= s.Length - 1; i++)
    {
        if (vowSet.Contains(s[i - k]))
            currentVowels--;

         if (vowSet.Contains(s[i]))
            currentVowels++;          

        resultVowels = Math.Max(resultVowels, currentVowels);
    }

    return resultVowels;

}

}

[Tesla-1i]

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        l = 0
        r = 0
        v = 0
        ans = 0
        n = len(s)
        while r < n:
            if s[r] in 'aeiou':
                v += 1
            if r - l + 1 > k:
                if s[l] in 'aeiou':
                    v -= 1
                l += 1
            r += 1
            ans = max(ans, v)    
        return ans

[tongxw]

思路

固定长度为k的滑动窗口，统计元音数量

class Solution {
    public int maxVowels(String s, int k) {
        int n = s.length();
        if (n < k) {
            return -1;
        }

        Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');
        int maxCount = 0;
        int count = 0;
        for (int i=0; i<n; i++) {
            if (i - k >= 0) {
                count -= vowels.contains(s.charAt(i-k)) ? 1 : 0;
            }

            count += vowels.contains(s.charAt(i)) ? 1 : 0;
            maxCount = Math.max(maxCount, count);

        }

        return maxCount;
    }
}

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

[linyang4]

思路

滑动窗口

维护一个变量count, 用于存储当前窗口里的元音字母数量

1. 滑动窗口的关键点在于左右指针移动的时机
   • 当左右指针之间的字符数量小于k时, 只需要移动右指针, 如果right指针的字符是元音字符, count++
   • 当左右指针之间的字符数量等于k时, 需要同时移动左右指针, 如果left指针的字符是元音字符, count--
2. 优化点: 如果某个窗口的count等于k时, 直接返回结果, 不需要再移动窗口了

代码

function isVowel(char) {
    return char === 'a' || char === 'e' || char === 'i' || char === 'o' || char === 'u'
}

var maxVowels = function(s, k) {
    let ans = count = left = right = 0
    const len = s.length
    if(len < k) { return ans }
    while(left <= len - k) {
        if (isVowel(s[right])) {
            count++
        }
        ans = Math.max(count, ans)
        if (ans === k) { return k }
        if (right - left === k - 1) {
            if (isVowel(s[left])) {
                count--
            }
            left++
        }
        right++
    }
    return ans
};

复杂度

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

[ZJP1483469269]

class Solution:

    def maxVowels(self, s: str, k: int) -> int:
        Set = set()
        Set.add('a')
        Set.add('e')
        Set.add('i')
        Set.add('o')
        Set.add('u')
        ans = 0
        for i in range(min(k,len(s))):
            if s[i] in Set:
                ans += 1
        l , r = 0 , k 
        cnt = ans
        while r < len(s):
            if s[l] in Set:
                cnt -= 1
            if s[r] in Set:
                cnt += 1
            l += 1
            r += 1
            ans = max(ans,cnt)

        return ans

[L-SUI]

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var maxVowels = function (s, k) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u'])
    let count = 0,
        l = 0,
        r = 0
    while (r < k) {//初始化大小k的窗口
        vowels.has(s[r]) && count++
        r++
    }
    let max = count
    while (r < s.length) {//不断移动窗口
        vowels.has(s[r]) && count++
        vowels.has(s[l]) && count--
        l++
        r++
        max = Math.max(max, count)//更新最大元音数
    }
    return max
};

[pwqgithub-cqu]

思路:滑动窗口

代码 class Solution { public int maxVowels(String s, int k) { int l = 0, r = 0; int len = s.length(); // window setup int res = 0; char[] words = s.toCharArray(); while(r < k){ res += isVowel(words[r]); r++; } r--; // sliding int curr = res; while(r < len - 1){ curr = curr - isVowel(words[l++]) + isVowel(words[++r]); res = Math.max(res,curr); } return res; }

private int isVowel(char test){
    if(test == 'a' || test == 'e' || test == 'i' || test == 'o' || test == 'u') return 1;
    else return 0;
}

} 时间复杂度:O(N) 空间复杂度:O(1)

[tangjy149]

思路

滑动窗口

代码

class Solution {
public:
    bool isOk(char temp){
        if(temp=='a' ||temp=='e' ||temp=='i' ||temp=='o' ||temp=='u'){
            return true;
        }
        return false;
    }
    int maxVowels(string s, int k) {
        int slow=0,fast=0;
        int ans=0;
        int temp=0;
        while(fast<s.size()){
            if(isOk(s[fast])) temp++;
            fast++;
            if(fast-slow==k){
                ans=max(ans,temp);
                if(isOk(s[slow])) temp--;
                slow++;
            }
        }
        return ans;
    }
};

[cszys888]

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        result = 0
        curr_count = 0
        for char in s[0:k]:
            if char in 'aeiou':
                curr_count += 1
        result = max(result, curr_count)

        for idx in range(k,len(s)):
            if s[idx - k] in 'aeiou':
                curr_count -= 1
            if s[idx] in 'aeiou':
                curr_count += 1
            result = max(result, curr_count)

        return result

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

[JudyZhou95]

Solution

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowel_set = set(['a', 'e', 'i', 'o', 'u'])

        p1 = 0
        max_len = 0
        cur_len = 0
        for p2 in range(k):
            if s[p2] in vowel_set:
                cur_len += 1

        max_len = cur_len 
        for p2 in range(k, len(s)):  

            if s[p2] in vowel_set:
                cur_len += 1
            if s[p1] in vowel_set:
                cur_len -= 1

            p1 += 1
            max_len = max(max_len, cur_len)
            if max_len == k: return k
        return max_len

Analysis

Maintain a window of length k. Keep updating the number of vowels in the current window. \ Time Cpmplexity: O(N)\ Space Complexity: O(1)

[xinhaoyi]

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

给你字符串 s 和整数 k 。

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

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

思路一：前缀和

构造前缀和，存元音字母个数，然后遍历前缀和数组即可

代码

class Solution {
    public int maxVowels(String s, int k) {
        //前缀和
        int[] numsOfVowels = new int[s.length()];
        if(isVowel(s.charAt(0))) numsOfVowels[0] = 1;
        for(int i = 1; i < s.length(); i++){
            numsOfVowels[i] = numsOfVowels[i - 1];
            if(isVowel(s.charAt(i))){
                numsOfVowels[i] ++;
            }
        }
        int max = Integer.MIN_VALUE;
        for(int start = 0, end = k - 1; end < s.length(); start++, end++ ){
            //构造初值
            if(start == 0){
                max = numsOfVowels[end];
                continue;
            }
            if((numsOfVowels[end] - numsOfVowels[start - 1]) > max){
                max = numsOfVowels[end] - numsOfVowels[start - 1];
            }
        }
        return max;
    }

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

复杂度分析

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

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

[haixiaolu]

思路

滑动窗口

代码 / Python

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set(['a', 'e', 'i', 'o', 'u'])
        count = 0

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

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

            if s[i] in vowels:
                count += 1
                result = max(result, count)
        return result 

复杂度分析

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

[rzhao010]

Thoughts Using set to check vowels, and traverse the string. Or sliding window

Code

    public int maxVowels(String s, int k) {
        if (s.length() < k) {
            return -1;
        }

        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++) {
            if (set.contains(s.charAt(i))) {
                count++;
            }
        }
        int res = count;
        for (int i = k; i < s.length() ; i++) {
            if (set.contains(s.charAt(i - k))) {
                count--;
            }
            if (set.contains(s.charAt(i))) {
                count++;
                res = Math.max(res, count);
            }
        }
        return res;
    }

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

[jiaqiliu37]

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ans = i = cnt = 0

        for j in range(len(s)):
            if s[j] in 'aeiou':
                cnt += 1
            if j - i >= k:
                if s[i] in 'aeiou':
                    cnt -= 1
                i += 1

            ans = max(ans, cnt)

        return ans

Time complexity O(n) Space complexity O(1)

[LannyX]

代码

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 maxNum = 0;
        for(int i = 0; i < k; i++){
            if(set.contains(s.charAt(i))){
                    maxNum++;
            }
        }
        int cur = maxNum;
        for(int i = 1; i < s.length() - k + 1; i++){
            if(set.contains(s.charAt(i - 1))){
                    cur--;
            }
            if(set.contains(s.charAt(i + k - 1))){
                    cur++;
            }
            maxNum = Math.max(maxNum, cur);
        }

        return maxNum;

    }
}

复杂度分析

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

[qiaojunch]

class Solution: def maxVowels(self, s: str, k: int) -> int: vowel = 'aeiou' maxcnt = count = 0

    ## do sliding window to calculate the count of vowel letter in each window
    for i in range(len(s)):

        ## start to slide window
        if i >= k:
            if s[i-k] in vowel:     ## s[i-k] falls out of window
                count -= 1

        if s[i] in vowel:
            count += 1

        maxcnt = max(maxcnt, count)

    return maxcnt

time: o(n) space: o(1)

[Zhang6260]

JAVA版本

该题主要是使用滑动窗口的思想。

class Solution {
    public int maxVowels(String s, int k) {
        int  max  = 0;
        int res = 0;
        for(int i=0;i<k;i++){
            if(fun(s.charAt(i))){
                res++;
            }
        }
        max = res;
        for(int i=k;i<s.length();i++){
            if(fun(s.charAt(i-k))){
                res--;
            }
            if(fun(s.charAt(i))){
                res++;
            }
            max = Math.max(res,max);
        }
        return max;
    }
    public boolean fun(char temp){
        if(temp=='a'||temp=='e'||temp=='i'||temp=='o'||temp=='u'){
            return true;
        }
        return false;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

[Toms-BigData]

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

思路

滑动窗口基础类型题目

golang代码

func maxVowels(s string, k int) (ans int) {
    if len(s) == 0 || k == 0 {
        return 0
    }
    l := 0
    ans = -1
    num := 0
    for i := 0; i < len(s); i++ {
        if i < k {
            if s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u' {
                num++
            }
        } else {
            if i == k{
                if num > ans {
                    ans = num
                }
            }
            if s[l] == 'a' || s[l] == 'e' || s[l] == 'i' || s[l] == 'o' || s[l] == 'u' {
                num--
            }
            if s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u' {
                num++
            }
            if num > ans {
                ans = num
            }
            if ans == k{
                return ans
            }
            l++
        }

    }
    if ans == -1 {
        return num
    }
    return
}

复杂度

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

[junbuer]

思路

• 滑动窗口 + 哈希表

代码

class Solution(object):
    def maxVowels(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        hashmap = set('aeiou')
        cnt = sum(1 for i in range(k) if s[i] in hashmap)
        ans = cnt 
        for i in range(k , len(s)):
            if s[i] in hashmap:
                cnt += 1
            if s[i - k] in hashmap:
                cnt -= 1
            ans = max(ans, cnt)
        return ans

复杂度分析

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

[1149004121]

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

思路

二分查找适合的高度，判断是否符合要求可以用dfs。

代码

var maxVowels = function(s, k) {
    let i = -1;
    let set = new Set(["a", "e", "i", "o", "u"])
    let temp = 0;
    let res = 0;
    const n = s.length;
    while(i < n - 1){
        i++;
        if(set.has(s[i])){
            temp++;
        };
        if(i >= k && set.has(s[i - k])){
            temp--;
        }
        res = Math.max(temp, res);
    };
    return res;
};

复杂度分析

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

[arteecold]

滑动加hash

不过这个的思路感觉比简单的题目要想的时间长很多

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        res = 0
        temp = 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,len(s)):
            temp += (s[i] in vowels) - (s[i-k] in vowels)
            res = max(temp,res)
            if res ==k: return k
        return res

O(n)

感觉大部分都是On

[zol013]

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ans = 0
        i = 0
        cnt = 0

        for j in range(len(s)):
            if s[j] in "aeiou":
                cnt += 1

            if j - i + 1 > k:
                if s[i] in 'aeiou':
                    cnt -= 1
                i += 1

            ans = max(ans, cnt)

        return ans

[WANGDI-1291]

代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        res = 0
        temp = 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,len(s)):
            temp += (s[i] in vowels) - (s[i-k] in vowels)
            res = max(temp,res)
            if res ==k: return k
        return res

• 时间复杂度：O（N）
• 空间复杂度：O（1）

[Myleswork]

思路

滑动窗口

维护一个大小为k的滑动窗口，在滑动的过程中动态更新元音的数量

代码

class Solution {
public:
    bool judge(char s){
        if(s == 'a' || s=='e'||s=='i'||s=='o'||s=='u') return true;
        return false;
    }
    int maxVowels(string s, int k) {
        int count = 0;
        int res = 0;
        for(int i = 0;i<s.length();i++){
            if(i<k){
                if(judge(s[i])) count++;
                res = max(count,res);
                continue;
            }
            if(res == k) return k;
            if(judge(s[i-k])) count--;
            if(judge(s[i])) count++;
            res = max(count,res);
        }
        return res;
    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

[alongchong]

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;
    }
}

[xuhzyy]

class Solution(object):
    def maxVowels(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        n = len(s)
        count, res, left, right = 0, 0, 0, 0
        words = ['a', 'e', 'i', 'o', 'u']
        for right in range(k):
            c = s[right]
            if c in words:
                count += 1
        res = count
        for right in range(k, n):
            if s[right] in words:
                count += 1
            if s[left] in words:
                count -= 1
            left += 1
            res = max(res, count)
        return res

[taojin1992]

/*
1 <= k <= s.length
1 <= s.length <= 10^5
s consists of lowercase English letters.

# Logic:
fixed window of size k 
a,e,i,o,u
adjust left and right, left starts at 0 ,ending at s.length() - k
check new in and out char, adjust count 

# Complexity:
Time:O(n), n = s.length()

Space: O(1), two pointers

# Tests:
s = "rhythms", k = 4

"abciiidef", 3

*/

class Solution {
    public int maxVowels(String s, int k) {
        int l = 0, r = 0;
        int maxVowelNum = 0, count = 0;
        while (l <= s.length() - k) {
            // increase the right boundary
            while (r < s.length() && r - l + 1 <= k) {
                if (s.charAt(r) == 'a' || s.charAt(r) == 'e' || s.charAt(r) == 'i' || s.charAt(r) == 'o' || s.charAt(r) == 'u') {
                   count++;
                }
                r++;
            }
            // track maxCount
            maxVowelNum = Math.max(maxVowelNum, count);
            // once we reach the size = k, increase the left to decrease the window size by 1
            if (s.charAt(l) == 'a' || s.charAt(l) == 'e' || s.charAt(l) == 'i' || s.charAt(l) == 'o' || s.charAt(l) == 'u') {
                count--;
            }
            l++;
        }
        return maxVowelNum;
    }
}

[pf135145]

代码

var maxVowels = function (s, k) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u'])
    let count = 0,
        l = 0,
        r = 0
    while (r < k) {
        vowels.has(s[r]) && count++
        r++
    }
    let max = count
    while (r < s.length) {
        vowels.has(s[r]) && count++
        vowels.has(s[l]) && count--
        l++
        r++
        max = Math.max(max, count)
    }
    return max
};

[Menglin-l]

approach: sliding window

---

code:

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';
    }
}

---

complexity:

Time: O(N)

Space: O(1)

[biaohuazhou]

思路

滑动窗口

代码

class Solution {
    public int maxVowels(String s, int k) {
        int n = s.length();

        int count = 0;
        //第一个窗口
        for (int i = 0; i < k; i++) {
            count += isVowels(s.charAt(i));
        }
        int ans = count;
        //窗口右移
        for (int i = k; i < n; i++) {
            //窗口右边的减去窗口左边的
            count += isVowels(s.charAt(i)) - isVowels(s.charAt(i - k));
            //更新ans
            ans = Math.max(ans, count);
        }
        return ans;
    }

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

}

复杂度分析 时间复杂度：$O(n)$ n为字符串长度 空间复杂度：$O(1)$

[wbcz]

public int maxVowels(String s, int k) {

if (s == null || s.length() < k)
    return 0;

int res = 0;
Set<Character> set = new HashSet<>(){{
    add('a');add('e');add('i');add('o');add('u');
}};

for (int i = 0; i < s.length() - k + 1; i++) {

    String sub = s.substring(i, i + k);
    int count = 0;

    for (int j = 0; j < sub.length(); j++)
        if (set.contains(sub.charAt(j)))
            count++;

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

return res;

}

[Richard-LYF]

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

    #  on  o1