Sponsored
Sponsored
This approach uses the sliding window technique to efficiently find the maximum number of vowels in any substring of length k.
We first calculate the number of vowels in the initial window of length k. Then, for each subsequent character, we slide the window by one character to the right: we remove the character that goes out of the window and add the one that comes into the window, updating our vowel count accordingly.
This ensures that we examine each character in the string only once, leading to an O(n) time complexity.
Time Complexity: O(n), where n is the length of the string. We iterate through the string with a constant number of operations for each character.
Space Complexity: O(1), as we use a fixed amount of extra space.
1using System;
2
3public class MaxVowelsSolution {
4 public int MaxVowels(string s, int k) {
5 string vowels = "aeiou";
6 int maxCount = 0, currentCount = 0;
7
8 for (int i = 0; i < k; i++) {
9 if (vowels.IndexOf(s[i]) >= 0) {
10 currentCount++;
11 }
12 }
13 maxCount = currentCount;
14
for (int i = k; i < s.Length; i++) {
if (vowels.IndexOf(s[i]) >= 0) {
currentCount++;
}
if (vowels.IndexOf(s[i - k]) >= 0) {
currentCount--;
}
maxCount = Math.Max(maxCount, currentCount);
}
return maxCount;
}
public static void Main(string[] args) {
var solution = new MaxVowelsSolution();
Console.WriteLine(solution.MaxVowels("abciiidef", 3));
}
}In C#, we leverage a vowel string for swift IndexOf checks to determine vowel presence. This method simulates sliding window logic by using indices to calculate the count of vowels in the current window. By sliding this window across the string and modifying currentCount as each character enters or exits the window, we determine the maximum number of vowels possible in any rolling substring of length k.
Another way to tackle this problem is to use a combination of prefix sums and binary search to precompute regions of vowels.
First, we establish a prefix sum array that accumulates the number of vowels encountered at each character index in the string. Then, we use a binary search within this prefix sum to efficiently find the maximum number of vowels in any moving window of length k.
This approach is more complex and is generally less optimal than the sliding window approach but provides an alternative methodology.
Time Complexity: O(n), for prefix sum construction and analysis.
Space Complexity: O(n), for the prefix sum array.
#include <vector>
#include <string>
using namespace std;
bool isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
int maxVowels(const string &s, int k) {
int n = s.size();
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + isVowel(s[i]);
}
int maxCount = 0;
for (int i = k; i <= n; ++i) {
maxCount = max(maxCount, prefix[i] - prefix[i - k]);
}
return maxCount;
}
int main() {
cout << maxVowels("abciiidef", 3) << endl;
return 0;
}The C++ version constructs a prefix sum array that records cumulative vowel counts. With this array, the maximum number of vowels in any substring of length k is the largest difference between prefix sums spaced by k indices, allowing for efficient lookups.