Java 中查找包含 K 个元音的 longest substring

这是Google、Amazon、TCS、Accenture等顶级IT公司面试中经常出现的问题。通过解决这个问题，可以考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将使用不同的方法和逻辑来查找 Java 中包含正好 K 个元音字符的最长子字符串。此外，我们还将为此创建 Java 程序。

问题陈述

我们给出一个包含大写和小写字母的字符串(str)和一个整数K。任务是找到包含正好 K 个元音字符（可能重复）的最长子字符串。

问题解决方案

朴素方法

任务是确定给定字符串的哪个子字符串最长，并且恰好包含 K 个元音字符。根据定义，元音字符是字母 a、e、i、o 和 u。我们需要找到给定字符串 s 和整数 K 的恰好包含 K 个元音字符的最长子字符串的长度。如果不存在这样的子字符串，则返回 0。

文件名：LongestSubstringKBruteForce.java

输出

 
Longest Substring Length: 9   

解释

此暴力方法使用两个嵌套循环来生成所有可能的子字符串。我们使用 isVowel() 方法来计算每个子字符串中的元音字符数。

如果计数等于 K，我们则更新迄今为止找到的最大长度。此方法的时空复杂度为 O(n^2)，其中 n 是字符串的长度。虽然它不是最快的方法，但它保证了准确性。

2. 滑动窗口法

这种优化方法维护一个在字符串上滑动的窗口，并调整其大小以确保它包含正好 K 个元音字符。

文件名：LongestSubstringKSlidingWindow.java

输出

 
Longest Substring Length: 9   

解释

在滑动窗口方法中，我们使用两个指针 left 和 right 来定义一个窗口。通过向右移动，我们扩大窗口并计算其中的元音字符数。如果元音字符数超过 K，窗口将从左侧收缩，通过移动 left 指针直到元音字符数恰好等于 K。

记录最长的允许窗口。使用这种方法，时间复杂度降低到 O(n)，提高了长字符串的效率。

3. 使用 HashMap 方法

此方法使用 HashMap 跟踪当前窗口中每个元音字符的出现次数。

文件名：LongestSubstringKHashMap.java

输出

 
Longest Substring Length: 9   

解释

在 HashMap 方法中，我们使用 HashMap 跟踪活动窗口中每个元音字符的出现次数。这使我们能够在调整窗口的同时有效控制元音字符的数量。

滑动窗口方法和窗口扩展和收缩的原理是相同的，但 HashMap 的使用提供了更好的元音字符控制。即使有额外的约束，这种策略也可以更灵活，但时间复杂度仍然是 O(n)。