【Day 43 】2024-09-26 - 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

[Fightforcoding]

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        n = len(s)
        if k > n:
            return 0
        def testv (arr):
            count = 0
            for char in arr:
                if char == 'a' or char == 'e' or char =='i' or char == 'o' or char == 'u':
                    count += 1
            return count

        maxn  = testv(s[:k])
        current = testv(s[:k])
        for i in range(k, n):
            if s[i] == 'a' or s[i] == 'e' or s[i] =='i' or s[i] == 'o' or s[i] == 'u':
                current += 1

            if s[i - k ] == 'a' or s[i - k ] == 'e' or s[i - k ]=='i' or s[i - k ] == 'o' or s[i - k] == 'u':
                current -= 1
            maxn = max(maxn, current)

        return maxn

Time: O(n)

Space: O(1)

[huizsh]

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

[zjy-debug]

代码

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

        # 计算第一个窗口的元音数量
        for i in range(k):
            if s[i] in vowels:
                currentVowelCount += 1

        maxVowelLength = currentVowelCount

        # 移动窗口
        for i in range(k, len(s)):
            if s[i] in vowels:
                currentVowelCount += 1
            if s[i - k] in vowels:
                currentVowelCount -= 1

            maxVowelLength = max(maxVowelLength, currentVowelCount)

        return maxVowelLength

[sleepydog25]

先打卡

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

        int maxVowels = 0;
        int currentVowelCount = 0;
        String vowels = "aeiou";

        // Count vowels in the first window
        for (int i = 0; i < k; i++) {
            if (vowels.indexOf(s.charAt(i)) != -1) {
                currentVowelCount++;
            }
        }
        maxVowels = currentVowelCount;

        // Slide the window
        for (int i = k; i < s.length(); i++) {
            if (vowels.indexOf(s.charAt(i - k)) != -1) {
                currentVowelCount--; // Remove the vowel going out of the window
            }
            if (vowels.indexOf(s.charAt(i)) != -1) {
                currentVowelCount++; // Add the new vowel coming into the window
            }
            maxVowels = Math.max(maxVowels, currentVowelCount);
        }

        return maxVowels;

    }

}

[godkun]

思路

• 滑动窗口
• 要先初始化窗口
• 再滑动窗口
• 窗口左侧索引是 s[i-k]

代码

go实现

func maxVowels(s string, k int) int {
    vowels := map[byte]bool{
        'a': true,
        'e': true,
        'i': true,
        'o': true,
        'u': true,
    }
    // 初始化窗口
    count := 0
    for i := 0; i < k; i++ {
        if vowels[s[i]] {
            count++
        }
    }
    maxCount := count
    for i := k; i < len(s); i++ {
        if vowels[s[i-k]] {
            count--
        }
        if vowels[s[i]] {
            count++
        }
        if count > maxCount {
            maxCount = count
        }
    }
    return maxCount
}

复杂度分析

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