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

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

题目

给你字符串 s 和整数 k 。

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

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

解题思路

这是一个典型的定长滑动窗口，解题思路为入-更新-出

入：下标为 i 的元素进入窗口，更新相关统计量。如果窗口左端点 i−k+1<0，则尚未形成第一个窗口，重复第一步。 更新：更新答案。一般是更新最大值/最小值。 出：下标为 i−k+1 的元素离开窗口，更新相关统计量，为下一个循环做准备。

注意边界: 出的时候窗口大小大小为k，出之后大小为k-1，此时R-L+1=k, L=R-k+1

代码

func isVowel(c byte) bool {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
}

func maxVowels(s string, k int) int {
    ans := 0
    cnt := 0

    for i := range len(s) {
        if isVowel(s[i]) {
            cnt++
            ans = max(ans, cnt)
        }
        if i < k - 1 {
            continue
        }
        // 将更新挪到入时的那一步可以剪枝
        if isVowel(s[i - k + 1]) {
            cnt--
        }
    }
    return ans
}

fn is_vowels(c: u8) -> bool {
    if c == b'a' || c == b'e' || c == b'i' || c == b'o' || c == b'u' {
        return true
    }
    false
}

impl Solution {
    pub fn max_vowels(s: String, k: i32) -> i32 {
        let s = s.as_bytes();
        let k = k as usize;
        let mut ans = 0;
        let mut vowel = 0;
        for (i, &c) in s.iter().enumerate() {
            if is_vowels(c) {
                vowel += 1;
                ans = ans.max(vowel);
            }
            if i < k - 1 {
                continue;
            }
            if is_vowels(s[i - k + 1]) {
                vowel -= 1;
            }
        }
        ans
    }
}