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, u).
 
Example 1:
Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Example 2:
Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3:
Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

Example 4:
Input: s = "rhythms", k = 4
Output: 0
Explanation: We can see that s doesn't have any vowel letters.

Example 5:
Input: s = "tryhard", k = 4
Output: 1

 
Constraints:

1 <= s.length <= 10^5
s consists of lowercase English letters.
1 <= k <= s.length

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Amortized analysis

Starter code: class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        

Solutions:
class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		n = len(s)
		vowel = set(['a', 'e', 'i', 'o', 'u'])
		i = 0
		res = 0
		while i < k:
			if s[i] in vowel:
				res += 1
			i += 1
		j = k
		i = 0
		maxV = res
		while j < n:
			if s[i] in vowel:
				res -= 1
			if s[j] in vowel:
				res += 1
			i += 1
			j += 1
			if maxV < res:
				maxV = res
		return maxV


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowels = set(['A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u'])
		res = 0
		cnt = 0
		for i in range(k):
			if s[i] in vowels:
				cnt += 1
		res = max(res, cnt)
		for i in range(k, len(s)):
			if s[i] in vowels:
				cnt += 1
			if s[i - k] in vowels:
				cnt -= 1
			res = max(res, cnt)
		return res


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		maxNum = -1
		currNum = 0
		vowels = 'aeiou'
		j = 0
		while j < k:
			if s[j] in vowels:
				currNum += 1
			j += 1
		maxNum = max(maxNum, currNum)
		for i in range(k, len(s)):
			if s[i] in vowels:
				currNum += 1
			if s[i - k] in vowels:
				currNum -= 1
			maxNum = max(maxNum, currNum)
		return maxNum


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowel = {'a', 'e', 'i', 'o', 'u'}
		cnt = 0
		for i in range(k):
			if s[i] in vowel:
				cnt += 1
		if cnt == k:
			return k
		i = 0
		res = cnt
		for j in range(k, len(s)):
			if s[i] in vowel:
				cnt -= 1
			if s[j] in vowel:
				cnt += 1
			i += 1
			if cnt == k:
				return k
			res = max(res, cnt)
		return res


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowel = 'aeiou'
		n = len(s)
		i = k
		window = s[:k]
		res = sum([1 for x in window if x in vowel])
		tmp = res
		while i < n:
			if s[i - k] in vowel:
				tmp -= 1
			if s[i] in vowel:
				tmp += 1
			res = max(res, tmp)
			i += 1
		return res


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowels = set('aeiou')
		init = len([x for x in s[:k] if x in vowels])
		ans = init
		for i in range(1, len(s) - k + 1):
			if s[i - 1] in vowels:
				init -= 1
			if s[i + k - 1] in vowels:
				init += 1
			ans = max(ans, init)
		return ans


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		ans = 0
		dic = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
		for i in range(k):
			if s[i] in dic:
				ans += 1
		i = 0
		j = k
		temp = ans
		while j < len(s):
			if s[j] in dic:
				temp += 1
			if s[i] in dic:
				temp -= 1
			ans = max(ans, temp)
			i += 1
			j += 1
		return ans


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowels = 'aeiou'
		num_vowels = sum((1 for i in range(k) if s[i] in vowels))
		max_vowels = num_vowels
		for removed_idx in range(0, len(s) - k):
			added_idx = removed_idx + k
			num_vowels += int(s[added_idx] in vowels) - int(s[removed_idx] in vowels)
			if num_vowels > max_vowels:
				max_vowels = num_vowels
		return max_vowels


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowels = {'a', 'e', 'i', 'o', 'u'}
		vowel_count = 0
		for i in range(k):
			if s[i] in vowels:
				vowel_count += 1
		max_vowels = vowel_count
		for i in range(k, len(s)):
			if s[i - k] in vowels:
				vowel_count -= 1
			if s[i] in vowels:
				vowel_count += 1
			max_vowels = vowel_count if vowel_count > max_vowels else max_vowels
		return max_vowels


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		truth_table = []
		for (idx, char) in enumerate(s):
			if char in ['a', 'e', 'i', 'o', 'u']:
				truth_table.append(idx)
		(pre_count, pre_idx, return_count) = (0, 0, 0)
		for (idx, vowel_idx) in enumerate(truth_table):
			if idx == 0:
				count = 1
				next_idx = idx + 1
			else:
				count = pre_count - 1
				next_idx = pre_idx + 1
			while next_idx < len(truth_table) and truth_table[next_idx] - vowel_idx + 1 <= k:
				count += 1
				pre_idx = next_idx
				next_idx += 1
			pre_count = count
			if count > return_count:
				return_count = count
		return return_count


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowel = set('aeiou')
		leftwindow = 0
		ans = 0
		temp = 0
		for rightwindow in range(len(s)):
			if rightwindow < k:
				if s[rightwindow] in vowel:
					temp += 1
					ans = max(temp, ans)
				continue
			leftChar = s[leftwindow]
			rightChar = s[rightwindow]
			if rightChar in vowel and leftChar in vowel:
				pass
			elif rightChar in vowel:
				temp += 1
			elif leftChar in vowel:
				temp -= 1
			ans = max(temp, ans)
			leftwindow += 1
		return ans


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		(maxVow, count) = (0, 0)
		for (i, j) in enumerate(s):
			if j in 'aeiou':
				count += 1
			if i >= k and s[i - k] in 'aeiou':
				count -= 1
			maxVow = max(maxVow, count)
		return maxVow


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowels = ['a', 'e', 'i', 'o', 'u']
		max_cnt = sum([1 for i in range(k) if s[i] in vowels])
		cnt = max_cnt
		for i in range(k, len(s)):
			if s[i] in vowels:
				cnt += 1
			if s[i - k] in vowels:
				cnt -= 1
			max_cnt = max(cnt, max_cnt)
		return max_cnt


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		ans = 0
		cur = 0
		for (j, c) in enumerate(s):
			cur += c in 'aeiou'
			if j >= k:
				cur -= s[j - k] in 'aeiou'
			ans = max(ans, cur)
		return max(ans, cur)


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vo = set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])
		(l, max_l, count) = (0, 0, 0)
		for i in range(len(s)):
			ch = s[i]
			if ch in vo:
				count += 1
			if i - l + 1 > k:
				if s[l] in vo:
					count -= 1
				l += 1
			max_l = max(max_l, count)
		return max_l


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		(su, res, vov) = (0, 0, ('a', 'e', 'i', 'o', 'u'))
		for (i, v) in enumerate(s):
			if v in vov:
				su += 1
			if i - k >= 0:
				if s[i - k] in vov:
					su -= 1
			res = max(res, su)
		return res


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowelMap = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
		for i in range(0, k):
			if s[i] in vowelMap:
				vowelMap[s[i]] += 1
		maxVowels = sum(vowelMap.values())
		for i in range(1, len(s) - k + 1):
			if s[i + k - 1] in vowelMap:
				vowelMap[s[i + k - 1]] += 1
			if s[i - 1] in vowelMap:
				vowelMap[s[i - 1]] -= 1
			maxVowels = max(maxVowels, sum(vowelMap.values()))
		return maxVowels


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		(m, beg, end) = (len(s), 0, 0)
		vowels = ['a', 'e', 'i', 'o', 'u']
		(maxi, count) = (0, 0)
		while end < m:
			if s[end] in vowels:
				count += 1
			if end - beg + 1 >= k:
				maxi = max(maxi, count)
				if s[beg] in vowels:
					count -= 1
				beg += 1
			end += 1
		return maxi


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowels = {'a', 'e', 'i', 'o', 'u'}
		(mx, vowelCount) = (0, 0)
		(l, r) = (0, 0)
		while r < len(s):
			if s[r] in vowels:
				vowelCount += 1
			r += 1
			while r - l == k and l < len(s):
				mx = max(vowelCount, mx)
				if s[l] in vowels:
					vowelCount -= 1
				l += 1
		return mx


class Solution:

	def maxVowels(self, s: str, k: int) -> int:

		def vowel_letters(ch):
			if ch in ['a', 'e', 'i', 'o', 'u']:
				return True
			return False
		temp = [1 if vowel_letters(i) else 0 for i in s]
		su = sum(temp[:k])
		m = su
		for i in range(k, len(temp)):
			su += temp[i] - temp[i - k]
			m = max([su, m])
		return m


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		ans = 0
		n = len(s)
		(i, j) = (0, 0)
		cnt = 0
		vowels = {'a', 'e', 'i', 'o', 'u'}
		while j < n:
			if s[j] in vowels:
				cnt += 1
			if j == k - 1:
				break
			else:
				j += 1
		ans = max(ans, cnt)
		while j + 1 < n:
			if s[i] in vowels:
				cnt -= 1
			i += 1
			j += 1
			if s[j] in vowels:
				cnt += 1
			ans = max(ans, cnt)
		return ans


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		total = res = 0
		for i in range(len(s)):
			if s[i] in 'aeiou':
				total += 1
			if i >= k - 1:
				res = max(res, total)
				if s[i - k + 1] in 'aeiou':
					total -= 1
		return res


class Solution:

	def maxVowels(self, S, K):
		N = len(S)
		L = [0] * (N + 1)
		for i in range(N):
			if S[i] in ['a', 'e', 'i', 'o', 'u']:
				L[i + 1] = 1
		for i in range(1, N + 1):
			L[i] += L[i - 1]
		i = 0
		j = K
		ans = 0
		while i <= N and j <= N:
			ans = max(ans, L[j] - L[i])
			i += 1
			j += 1
		return ans


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		is_a_vowel = lambda letter: letter in 'aeiou'
		count = 0
		maximum_vowels = 0
		left = 0
		for right in range(len(s)):
			if right < k:
				count = count + 1 if is_a_vowel(s[right]) else count
				maximum_vowels = max(maximum_vowels, count)
			else:
				count = max(0, count - 1) if is_a_vowel(s[left]) else count
				count = count + 1 if is_a_vowel(s[right]) else count
				left = left + 1
				maximum_vowels = max(maximum_vowels, count)
		return maximum_vowels


class Solution:

	def maxVowels(self, s, k):
		(vcnt, res) = (dict(), 0)
		for (i, c) in enumerate(s):
			if i - k >= 0 and s[i - k] in 'aeiou':
				vcnt[s[i - k]] -= 1
			if c in 'aeiou':
				vcnt[c] = vcnt.get(c, 0) + 1
			res = max(res, sum(vcnt.values()))
		return res

class Solution:

	def maxVowels(self, s, k):
		(res, cnt) = (0, 0)
		for (i, c) in enumerate(s):
			cnt += (c in 'aeiou') - (i - k >= 0 and s[i - k] in 'aeiou')
			if cnt > res:
				res = cnt
		return res


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		max_val = 0
		tmp = 0
		i = 0
		he = len(s)
		for i in range(k):
			if s[i] in 'aeiou':
				tmp += 1
				if tmp == k:
					return k
		if tmp > max_val:
			max_val = tmp
		for i in range(k, he):
			if s[i - k] in 'aeiou':
				tmp -= 1
			if s[i] in 'aeiou':
				tmp += 1
			if tmp > max_val:
				max_val = tmp
		return max_val


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		i = 0
		j = i + k - 1
		cc = 0
		for k in range(i, j + 1):
			if s[k] == 'a' or s[k] == 'e' or s[k] == 'i' or (s[k] == 'o') or (s[k] == 'u'):
				cc += 1
		max_c = 0
		while j < len(s):
			if cc > max_c:
				max_c = cc
			if s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
				cc -= 1
			i += 1
			j += 1
			if j < len(s):
				if s[j] == 'a' or s[j] == 'e' or s[j] == 'i' or (s[j] == 'o') or (s[j] == 'u'):
					cc += 1
		return max_c


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowels = {'a', 'e', 'i', 'o', 'u'}
		current = 0
		maxx = 0
		(start, end) = (0, 0)
		if k == 0:
			return 0
		while end < min(start + k, len(s)):
			if s[end] in vowels:
				current += 1
			end += 1
		if end == len(s):
			return current
		while end < len(s):
			maxx = max(maxx, current)
			if s[start] in vowels:
				current -= 1
			start += 1
			if s[end] in vowels:
				current += 1
			end += 1
		return max(maxx, current)


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowel = 0
		max_vowel = 0
		front = 0
		for i in range(len(s)):
			if s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
				vowel += 1
				print(s[i])
			if i >= k - 1:
				max_vowel = max(max_vowel, vowel)
				front = s[i - k + 1]
				if front == 'a' or front == 'e' or front == 'i' or (front == 'o') or (front == 'u'):
					vowel -= 1
		return max_vowel


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		if not s or not k:
			return 0
		max_vowels = 0
		start_pointer = 0
		end_pointer = k - 1
		vowels = {'a', 'e', 'i', 'o', 'u'}
		num_curr_window_vowels = 0
		for i in range(k):
			if s[i] in vowels:
				num_curr_window_vowels += 1
		max_vowels = max(max_vowels, num_curr_window_vowels)
		while end_pointer < len(s) - 1:
			if s[start_pointer] in vowels:
				num_curr_window_vowels -= 1
			start_pointer += 1
			end_pointer += 1
			if s[end_pointer] in vowels:
				num_curr_window_vowels += 1
			max_vowels = max(max_vowels, num_curr_window_vowels)
		return max_vowels


def window_sums(bits, width):
	coll = []
	pointer = 0
	total = 0
	for elem in bits:
		if len(coll) < width:
			coll.append(elem)
			total += elem
			if len(coll) == width:
				yield total
		else:
			total += elem - coll[pointer]
			coll[pointer] = elem
			pointer = (pointer + 1) % width
			yield total

class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		bits = (ch in 'aeiou' for ch in s)
		sums = window_sums(bits, k)
		return max(sums)


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowel = set({'a', 'e', 'i', 'o', 'u'})
		curr = 0
		maxx = 0
		for i in range(k):
			if s[i] in vowel:
				curr += 1
				maxx += 1
		for i in range(1, len(s) - k + 1):
			if s[i + k - 1] in vowel:
				curr += 1
			if s[i - 1] in vowel:
				curr -= 1
			if curr == k:
				return curr
			if curr >= maxx:
				maxx = curr
		return maxx


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		vowels = {'a', 'e', 'i', 'o', 'u'}
		count = 0
		maxCount = 0
		i = 0
		for j in range(len(s)):
			if s[j] in vowels:
				count += 1
			if j >= k and s[j - k] in vowels:
				count -= 1
			maxCount = max(maxCount, count)
		return maxCount


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		maks = 0
		string = ''
		count = 0
		lenght = 0
		for l in s:
			if l == 'a' or l == 'e' or l == 'i' or (l == 'o') or (l == 'u'):
				count += 1
			string += l
			lenght += 1
			if lenght == k:
				if count > maks:
					maks = count
				if string[0] == 'a' or string[0] == 'e' or string[0] == 'i' or (string[0] == 'o') or (string[0] == 'u'):
					count -= 1
				lenght -= 1
				string = string[1:k]
		return maks


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		self.vowels = ['a', 'e', 'i', 'o', 'u']

		def isVowel(char):
			return char in self.vowels
		i = 0
		j = 0
		cur_count = 0
		result = 0
		length = len(s)
		while i < length and j < length:
			if isVowel(s[j]):
				cur_count += 1
			if j - i + 1 >= k:
				result = max(result, cur_count)
				if isVowel(s[i]):
					cur_count -= 1
				i += 1
			j += 1
		return result


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		a = s[:k]
		d = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}

		def checkVowels():
			total = 0
			for key in d:
				total += d[key]
			return total
		for c in s[:k]:
			if c in d:
				d[c] += 1
		total = checkVowels()
		i = 1
		while i <= len(s) - k:
			prev = s[i - 1]
			if prev in d:
				d[prev] -= 1
			nxt = s[i + k - 1]
			if nxt in d:
				d[nxt] += 1
			total = max(total, checkVowels())
			i += 1
		return total


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		currMax = 0
		curr = 0
		vowels = set(['a', 'e', 'i', 'o', 'u'])
		for (i, c) in enumerate(s):
			if c in vowels:
				curr += 1
			if i >= k and s[i - k] in vowels:
				curr -= 1
			currMax = max(curr, currMax)
			if currMax == k:
				break
		return currMax


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		memo = collections.defaultdict(lambda : 0)
		i = 0
		res = 0
		vowels = set('aeiou')
		for j in range(len(s)):
			if s[j] in vowels:
				memo[s[j]] += 1
			if j - i + 1 == k:
				res = max(res, sum(memo.values()))
				if s[i] in memo:
					memo[s[i]] -= 1
					if memo[s[i]] == 0:
						del memo[s[i]]
				i += 1
		return res


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		cnt = i = ans = 0
		for j in range(len(s)):
			c = s[j]
			cnt += s[j] in 'aeiou'
			if j >= k:
				cnt -= s[i] in 'aeiou'
				i += 1
			if j >= k - 1:
				ans = max(ans, cnt)
		return ans


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		temp = defaultdict(lambda : 0)
		for i in range(k):
			temp[s[i]] += 1
		ans = sum((temp[i] for i in 'aeiou'))
		for i in range(k, len(s)):
			temp[s[i - k]] -= 1
			temp[s[i]] += 1
			ans = max(ans, sum((temp[i] for i in 'aeiou')))
		return ans


from collections import Counter

class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		c = Counter(s[:k])
		m = sum([c[x] for x in 'aeiou'])
		for i in range(len(s) - k):
			c[s[i]] -= 1
			c[s[i + k]] += 1
			m = max(m, sum([c[x] for x in 'aeiou']))
		return m


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		_start = 0
		_end = 0
		_max = 0
		start = 0
		length = 0
		count = 0
		for end in range(len(s)):
			length += 1
			if self.check(s[end]):
				count += 1
			if length > k:
				if self.check(s[start]):
					count -= 1
				start += 1
			if count > _max:
				_max = count
				_start = start
				_end = end
		return _max

	def check(self, ch):
		vowels = ['a', 'e', 'i', 'o', 'u']
		for vowel in vowels:
			if ch == vowel:
				return True
		return False


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		l = 0
		r = 0
		v_set = {'a', 'e', 'i', 'o', 'u'}
		window_len = 0
		count = 0
		max_len = 0
		while r < len(s):
			if window_len < k:
				if s[r] in v_set:
					count += 1
				window_len += 1
			else:
				print((window_len, count, s[r]))
				if count == k:
					max_len = k
					return max_len
				else:
					max_len = max(count, max_len)
					if s[l] in v_set:
						count -= 1
					l += 1
					window_len -= 1
					if s[r] in v_set:
						count += 1
					window_len += 1
			r += 1
		max_len = max(count, max_len)
		return max_len


class Solution:

	def maxVowels(self, s: str, k: int) -> int:
		i = 0
		j = 0
		cur_max = 0
		maxx = 0
		for i in range(len(s)):
			if s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
				cur_max += 1
			if i - j + 1 > k:
				if s[j] == 'a' or s[j] == 'e' or s[j] == 'i' or (s[j] == 'o') or (s[j] == 'u'):
					cur_max -= 1
				maxx = max(cur_max, maxx)
				j += 1
			maxx = max(cur_max, maxx)
		return maxx