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

[songyy5517]

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.

Intuition The problem is to find a substring of length k with the most vowels. So we need to check every substring of length k in the original string. Therefore, we can loop through the string with a sliding window. For each step, we calculate the number of vowels in the current substring and compare it with the global maximum.

[songyy5517]

Approach: Sliding Window

1. Exception handling;
2. Define variables and initiate:
   • num: the number of vowels in str[0:k-1];
   • max = num: the global maximum of vowels.
3. Iterate over the string with the sliding window:
   • Calculate the number of vowels in the current window, and compare with the global maximum.
4. Return the global maximum max.

Complexity Analysis

• Time complexity: $O(N)$ , iterating over the entire string takes $O(N)$ time;
• Space complexity: $O(1)$, additionally define constant-level variables.

[songyy5517]

class Solution {
    public int maxVowels(String s, int k) {
        // 思路：滑动窗口
        // 1. 异常处理
        if (s == null || s.length() < k)
            return 0;

        // 2. 变量定义
        int sum = 0;
        for (int i = 0; i < k; i++){
            sum += isVowel(s.charAt(i));
        }
        int max_sum = sum;

        // 3. 遍历字符串
        for (int i = k; i < s.length(); i++){
            sum = sum + isVowel(s.charAt(i)) - isVowel(s.charAt(i - k));
            max_sum = Math.max(max_sum, sum);
        }

        return max_sum;
    }

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

[songyy5517]

2024/5/13