1456. Determine the maximum number of vowels in a string.

Leetcode-cn.com/problems/ma…

Topic describes

I give you the string S and the integer k. Return the maximum number of vowels that can be contained in a single substring of length K in the string s. The vowels in English are (a, e, I, O, u). Example 1: Input: s = "abCIiidef ", k = 3 Output: 3 Explanation: The substring "iii" contains three vowels. Example 2: Input: s = "aeiou", k = 2 Output: 2 Description: Any substring of length 2 contains two vowels. Example 3: Input: s = "leetcode", k = 3 Output: 2 Explanation: "lee", "eet", and "ode" all contain two vowels. Example 4: Input: S = "rhythms", k = 4 Output: 0 Explanation: The string S does not contain any vowels. Example 5: Input: s = "tryhard", k = 4 Output: 1 Warning: 1 <= S. length <= 10^5 s consists of lowercase letters 1 <= k <= S. LengthCopy the code

Train of thought

Calculate the maximum value by sliding through the window

code

  • Language support: Python3

Python3 Code:


class Solution:
    def maxVowels(self, s: str, k: int) - >int:
        coreDic = dict()
        coreDic = {"a":1."e":1."i":1."o":1."u":1}
        res,temp = 0.0
        Form a sliding window like k first
        for i in s[:k]:
            if i in coreDic:
                temp += 1
        if len(s) == k : return temp
        res = temp
        # Start sliding window, put old -1, new +1
        for index,val in enumerate(s[k:]):
            if s[index] in coreDic:
                temp -= 1
            if val in coreDic:
                temp += 1
            res = max(temp,res)
        return res

if __name__ == '__main__':
    s = "abciiidef"
    k = 3
    result = Solution().maxVowels(s,k)
    print(result)

Copy the code

Complexity analysis

Let n be the length of the array.

  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)