在本文中,我们将研究一个与字符串和 Sliding-Window Algorithm相关的有趣问题。问题是 :"Given a String we have to Find the Maximum Number of Vowel Letters present in any Substring of the String, with the length of each Substring equal to K."
"Given a String we have to Find the Maximum Number of Vowel Letters present in any Substring of the String, with the length of each Substring equal to K."
让我们通过一些示例输入来理解这个语句:
Input: String = "java2blog" K = 3 Output: 2 Explanation: The Substrings with length K=3 for the Given String are: "jav" , "ava", "va2", "a2b", "2bl", "blo", "log". Out of which the Substring "ava" has the maximum number of vowels i.e. 2. Input: String = "looijk" K = 3 Output: 3 (Substring "ooi" has Maximum Vowel Letters).
现在,我们将讨论解决问题的不同方法并分析它们的复杂性。
基本上,我们将遍历字符串的长度并生成给定长度 K 的 所有子字符串使用包类中substring()存在的方法。String``java.lang
substring()
String``java.lang
我们保留一个变量 maxVowels,它将用于跟踪子字符串的最大元音。因此,对于每个子字符串,我们计算其中的元音数量并更新 maxVowels。
为了计算子字符串中元音的数量,我们实现countVowelsInSubstring()了,一个给定子字符串的方法将返回其中元音的数量。
countVowelsInSubstring()
让我们看一下这种方法的代码:
public class MaxVowelsSubstring { static int maxVowelsInSubstring(String s,int k) { int n = s.length(); int maxVowels = 0; // we iterate till n-k th position of the string for(int i = 0;i < n - k ;i++) { // We generate the substring of length k using substring(). String sub_s = s.substring(i,i+k); //then count the vowels in the substring int vowels = countVowelsInSubstring(sub_s); // update maxVowels if current vowels is greater. maxVowels = Math.max(maxVowels,vowels); } return maxVowels; } static int countVowelsInSubstring(String s) { int countVowels = 0; for(int i=0; i<s.length();i++) { //get current char char ch = s.charAt(i); // check if it is a vowel and increment count. if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ) countVowels++; } return countVowels; } public static void main(String args[]) { String str = "java2blog"; int k = 3; int result = maxVowelsInSubstring(str,k); System.out.println("The Maximum Vowels present in the Substring of size "+k+" is : "+result); } }
Output:
The Maximum Vowels present in the Substring of size 3 is : 2
Time Complexity:`使用方法生成大小为 K 的子字符串`substring()`需要 O(K) 时间,我们为 NK 个字符执行此操作需要总`O( (N-K) * K )`时间。现在,对于每个大小为 K 的子串,我们计算其中的元音,这需要总时间,所以总体 [时间复杂度](https://java2blog.com/introduction-to-complexity-of-algorithm/ “时间复杂度” ) 将是: . 对于这个问题,这是一个幼稚的解决方案。`O( K * K) = O(K2)``O( N*K -K2 + K2) = O(N * K)
这种方法背后的目的是为这个问题提供一个线性运行时解决方案(O(n))。为此,我们将使用滑动窗口方法的思想。我们遵循以下步骤:
countVowels
maxVowels
"java2blog"
K
i - k
现在,让我们看一下上述方法在代码中的实现:
public class MaxVowelsSubstring { static boolean isVowel(char ch) { if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') return true; return false; } static int maxVowelsInSubstring(String s,int k) { int countVowels=0; //Maintains overall count of vowels // Count vowels in First Window for(int i=0;i<k;i++) { if(isVowel(s.charAt(i))) countVowels++; } int maxVowels = 0; // Update maxVowels for first window. if(maxVowels< countVowels) maxVowels = countVowels; for(int i=k;i<s.length();i++) { if(isVowel(s.charAt(i))) // check if current char is a vowel. countVowels++; if(isVowel(s.charAt(i-k))) // check if starting of previous window was a vowel countVowels--; maxVowels = Math.max(maxVowels,countVowels); // update maxVowels for each window. } return maxVowels; } public static void main(String args[]) { String str = "java2blog"; int k = 3; int result = maxVowelsInSubstring(str,k); System.out.println("The Maximum Vowels present in the Substring of size "+k+" is : "+result); } }
Time Complexity:基本上,我们在字符串 N 的长度上滑动窗口,并且只遍历每个字符一次。对于每个字符,我们检查它是否是一个 O(1) 操作的元音。所以这种方法的时间复杂度是O(N)并且给出了问题的最佳解决方案。
Time Complexity:
O(N)
这就是给定长度的子字符串中元音的最大数量,您可以尝试使用考虑所有边缘情况的不同示例的代码。
原文链接:https://codingdict.com/