查找定长子串中元音的最大数目 – FrancisSoung

要解决这个问题，可以使用滑动窗口技术来找到给定字符串中包含最多元音的定长子串。滑动窗口是一种高效的算法，适用于这种需要处理连续子数组或子字符串的问题。

问题描述

给定一个字符串和一个整数 𝑘k，找到长度为 𝑘k 的子串中包含最多元音的子串，并返回该子串中元音的数量。

步骤

初始化滑动窗口：首先计算第一个窗口（即字符串的前 𝑘k 个字符）中的元音数量。
滑动窗口：然后移动窗口，每次移动一位，更新窗口中的元音数量。
记录最大值：在移动窗口的过程中，记录窗口中元音数量的最大值。

代码实现

public class MaxVowelsInSubstring {
    public static void main(String[] args) {
        String s = "abciiidef";
        int k = 3;
        System.out.println(maxVowels(s, k)); // Output: 3
    }

    public static int maxVowels(String s, int k) {
        int maxVowels = 0;
        int currentVowels = 0;
        int n = s.length();

        // 检查字符是否为元音的辅助函数
        boolean isVowel(char ch) {
            return "aeiouAEIOU".indexOf(ch) != -1;
        }

        // 计算第一个窗口中的元音数量
        for (int i = 0; i < k; i++) {
            if (isVowel(s.charAt(i))) {
                currentVowels++;
            }
        }

        // 使用第一个窗口中的元音数量初始化 maxVowels
        maxVowels = currentVowels;

        // Slide the window over the string
        for (int i = k; i < n; i++) {
            if (isVowel(s.charAt(i - k))) {
                currentVowels--;
            }
            if (isVowel(s.charAt(i))) {
                currentVowels++;
            }
            // 更新找到的最大元音数
            maxVowels = Math.max(maxVowels, currentVowels);
        }

        return maxVowels;
    }
}

解释

初始化：
- maxVowels 用于记录最大元音数量。
- currentVowels 用于记录当前窗口中的元音数量。
- isVowel 是一个辅助方法，用于检查字符是否为元音。
计算第一个窗口的元音数量：
- 遍历字符串的前 𝑘k 个字符，计算元音数量。
滑动窗口：
- 从第 𝑘k 个字符开始，逐个字符向右移动窗口。
- 每次移动时，更新 currentVowels，即减去窗口左边移出的字符的元音数量，增加窗口右边新进入字符的元音数量。
- 更新 maxVowels，记录当前窗口中的最大元音数量。

这个算法的时间复杂度是 𝑂(𝑛)O(n)，其中 𝑛n 是字符串的长度，因为我们只需遍历字符串一次。