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

Problem

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

1. 题目简述

给出一个字符串s和一个正整数k，返回以k长度的所有子字符串包含元音字母的最大值。例如：

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

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

2. 算法思路

Sliding Window

这道题一眼就能看出来是sliding window，初始化以后每次移动一位，记录历史最大值。

3. 解法

1. Sliding Window

使用Arrays.copyOfRange(int[] data, int start, int end)函数，写起来简洁，但是有点慢，而且耗空间大，因为要截取数组。

class Solution {
    public int maxVowels(String s, int k) {
        int tempVowels = 0, maxVowels = 0, startIndex = 0, endIndex = k;
        int length = s.length();

        for (int i = 0; i < k; i++) {
            if (isVowel(s.charAt(i))) {
                tempVowels++;
            }
        }

        maxVowels = tempVowels;
        while (endIndex < length) {
            if (isVowel(s.charAt(endIndex))) {
                tempVowels++;
            }
            if (isVowel(s.charAt(startIndex))) {
                tempVowels--;
            }
            endIndex++;
            startIndex++;
            maxVowels = Math.max(maxVowels, tempVowels);
        }

        return maxVowels;
    }

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