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

Description of Problem

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.

Example 1:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3:

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

Constraints:

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

Solution

Tags: Sliding Window Two Pointers

Explanation

Imagine that there is a Double-linked list (deque) that store exactly k elements:

When a new character comes, we push it into the back of the deque and count the number of vowels.
When we move the window, we pop the element from the front of the deque.

Code

impl Solution {
    pub fn max_vowels(s: String, k: i32) -> i32 {
        let mut s = s.as_bytes();
        let (n,k) = (s.len(), k as usize);
        let mut count = 0;
        let mut max_count = 0;

        for i in 0..k {
            let c = s[i];
            match c {
                97 | 101 | 105 | 111 | 117 => {
                    count+=1;
                },
                _ => {}
            }
        }
        
        max_count = max_count.max(count);

        for i in k..n{
            let d = s[i-k];
            match d {  
                97 | 101 | 105 | 111 | 117 => {
                    count-=1;
                },
                _ => {}
            }

            let c = s[i];
            match c {
                97 | 101 | 105 | 111 | 117 => {
                    count+=1;
                },
                _ => {}
            }
            max_count = max_count.max(count);
        }
        return max_count;
    }
}

Complexity

n is length of String s

Time Complexity

\( T(n) = \Theta(n) \)

Auxiliary Space

\( S(n) = O(1) \)

Leetbook