Maximum Number of Vowels in a Substring of Given Length — LeetCode 1456 Python Solution
MediumStringSliding Window
- Problem
- #1456
- Pattern
- Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k. Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.
Example
- Input
- s = "abciiidef", k = 3
- Output
- 3
- Explanation
- The substring "iii" contains 3 vowel letters.
Python solution
Python
class Solution:
def maxVowels(self, s: str, k: int) -> int:
vowels = set("aeiou")
ans = cnt = sum(c in vowels for c in s[:k])
for i in range(k, len(s)):
cnt += int(s[i] in vowels) - int(s[i - k] in vowels)
ans = max(ans, cnt)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the string s |
| Space | O(1) auxiliary |
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
LeetCode 1044Longest Duplicate SubstringHardLeetCode 1208Get Equal Substrings Within BudgetMediumLeetCode 1234Replace the Substring for Balanced StringMediumLeetCode 1839Longest Substring Of All Vowels in OrderMediumLeetCode 1871Jump Game VIIMediumLeetCode 1888Minimum Number of Flips to Make the Binary String AlternatingMedium
On a study list
This problem is on LeetCode 75.
Frequently asked questions
- How hard is LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length?
- LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length?
- The Python solution on this page runs in O(n), where n is the length of the string s.
- What is the space complexity of LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length cover?
- LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length is tagged String and Sliding Window on LeetCode.