SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem requires finding the maximum number of vowels in any substring of a given length k in the input string s. The function returns this maximum number of vowels.

Intuition

To efficiently find the maximum number of vowels in a substring of length k, a sliding window approach can be used. This approach allows us to keep track of the number of vowels in the current window and update the count as the window slides over the string.

Approach

1. Initialize a set of vowels: First, create a set containing all the vowels (a, e, i, o, u) to easily check if a character is a vowel.

2. Sliding Window Initialization: Start by examining the first k characters of the string. Count the number of vowels in this initial window and store the count.

3. Slide the Window: Move the window one character to the right at each step. Update the count by removing the effect of the character that is sliding out of the window and adding the effect of the character that is sliding into the window.

4. Track the Maximum Count: During each iteration, track the maximum number of vowels found in any window of length k.

5. Return the Result: After examining all possible windows, return the maximum count of vowels.

Complexity

Time Complexity:

O(n), where n is the length of the string s. The sliding window approach allows us to examine each character in the string exactly once.

Space Complexity:

O(1), as we use a fixed amount of extra space for the set of vowels and a few integer variables.

Code

C++

class Solution {
public:
    int maxVowels(std::string s, int k) {
        std::unordered_set<char> target = {'a', 'e', 'i', 'o', 'u'};
        std::vector<bool> substr;
        int n = 0, result = 0;

        for (int i = 0; i < k; ++i) {
            if (target.count(s[i])) {
                substr.push_back(true);
                ++n;
            } else {
                substr.push_back(false);
            }
        }
        result = n;

        for (int i = k; i < s.length(); ++i) {
            bool first = substr.front();
            substr.erase(substr.begin());
            substr.push_back(target.count(s[i]));
            if (first) {
                --n;
            }
            if (target.count(s[i])) {
                ++n;
            }
            result = std::max(result, n);
        }

        return result;
    }
};

Python

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        target = set('aeiou')
        substr = []
        n = 0
        result = 0

        for i in range(k):
            if s[i] in target:
                substr.append(True)
                n += 1
            else:
                substr.append(False)
        result = n

        for i in range(k, len(s)):
            first = substr.pop(0)
            substr.append(s[i] in target)
            if first:
                n -= 1
            if s[i] in target:
                n += 1
            result = max(result, n)

        return result

Java

class Solution {
    public int maxVowels(String s, int k) {
        Set<Character> target = new HashSet<>();
        target.add('a');
        target.add('e');
        target.add('i');
        target.add('o');
        target.add('u');

        int n = 0, result = 0;
        boolean[] substr = new boolean[k];

        for (int i = 0; i < k; ++i) {
            if (target.contains(s.charAt(i))) {
                substr[i] = true;
                ++n;
            } else {
                substr[i] = false;
            }
        }
        result = n;

        for (int i = k; i < s.length(); ++i) {
            boolean first = substr[0];
            System.arraycopy(substr, 1, substr, 0, k - 1);
            substr[k - 1] = target.contains(s.charAt(i));

            if (first) {
                --n;
            }
            if (target.contains(s.charAt(i))) {
                ++n;
            }
            result = Math.max(result, n);
        }

        return result;
    }
}

JavaScript

var maxVowels = function (s, k) {

    let target = ['a', 'e', 'i', 'o', 'u'];
    let substr = [];
    let n = 0;
    let result = 0;
    for (let i = 0; i < k; i++) {
        if (target.includes(s[i])) {
            substr.push(true)
            n++
        } else {
            substr.push(false)
        }
    }
    result = n;
    for (let i = k; i < s.length; i++) {
        let first = substr.shift();
        substr.push(target.includes(s[i]));
        if (first) {
            n--;
        };
        if (target.includes(s[i])) {
            n++;
        };
        result = Math.max(result, n);
    }
    return result;
};