leetcode
leetcode 1301 ~ 1350
定长子串中元音的最大数目

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

难度:

标签:

题目描述

代码结果

运行时间: 70 ms, 内存: 16.4 MB


/*
 * Problem: Find the maximum number of vowels in a substring of length k in a given string s.
 * Approach: Using Java Streams, we can simplify the iteration and calculation of vowels.
 * We use IntStream to iterate over the possible starting indices of the substrings.
 */

import java.util.Set;
import java.util.HashSet;
import java.util.stream.IntStream;

public class Solution {
    public int maxVowels(String s, int k) {
        // Define the set of vowel characters
        Set<Character> vowels = new HashSet<>(Set.of('a', 'e', 'i', 'o', 'u'));

        // Using IntStream to iterate over the possible starting indices
        return IntStream.rangeClosed(0, s.length() - k)
                .map(i -> (int) s.substring(i, i + k).chars()
                        .filter(c -> vowels.contains((char) c)).count())
                .max().orElse(0);
    }
}

解释

方法:

这个题解使用了滑动窗口的方法来解决问题。首先,它计算了字符串s的前k个字符中元音字母的数量,并将其存储在变量max0中。接下来,它遍历从第k个字符到字符串末尾的每个字符。在每次迭代中,它移除窗口最左侧的字符(如果它是元音字母,则从当前计数中减去1),并添加新的右侧字符(如果它是元音字母,则在当前计数中加1)。在每次迭代后,它会检查当前的元音字母计数是否是到目前为止遇到的最大值,并相应地更新max0。最终,max0将包含s中任何长度为k的子字符串可以含有的最大元音字母数量。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在计算初始窗口的元音字母数时不直接使用滑动窗口的方法,而是单独进行处理?
在算法开始时单独计算初始窗口的元音字母数是为了初始化元音字母的计数基础,从而为滑动窗口提供起始点。直接使用滑动窗口方法需要先有一个基准窗口的元音数,这样在后续滑动时,只需要做增减调整,避免了每次都要重新计算整个窗口的元音字母数,从而提高了效率。
🦆
如果字符串s的长度小于k,这个算法是否还能正确执行,如果不能,应如何修改代码以处理这种边界情况?
如果字符串s的长度小于k,按照当前算法逻辑,将会在尝试访问不存在的索引时引发错误。为了处理这种情况,可以在函数开始时添加一个检查条件:如果字符串长度小于k,则直接返回0,因为不可能有长度为k的子字符串。
🦆
在滑动窗口中,当移除最左侧的字符和添加最右侧的字符后,为何立即检查并更新最大元音字母数而不是在某些特定的点进行统一更新?
在每次滑动窗口后立即检查并更新最大元音字母数可以确保不遗漏任何可能的最大值。如果推迟到特定点统一更新,可能会错过中间的一些最大值情况。此外,实时更新可以保持算法的简洁性,并实时反映最新的计算结果。
🦆
代码中没有显式地检查字符串s是否只包含小写字母,这是否会影响算法的准确性,特别是在处理含有大写元音字母的字符串时?
是的,如果字符串s包含大写元音字母,当前的算法将无法正确识别并计数这些元音字母,因此会影响算法的准确性。为了解决这个问题,可以在检查字符是否为元音字母前,先将字符串s转换为全小写,或者在元音字符集中加入大写元音字母('AEIOU')。

相关问题