00:00:00

Description

Editorial

Peak Vowel Count in Window

MEDIUM20 pts

You are given a lowercase English string s and a positive integer k representing the window size. Your task is to find the maximum number of vowel characters that can appear in any contiguous segment (substring) of exactly k characters within the string.

A vowel in the English alphabet is defined as one of the following five characters: 'a', 'e', 'i', 'o', or 'u'.

You must scan through all possible contiguous windows of size k in the string and determine which window contains the highest concentration of vowels. Return this maximum count as an integer.

Key Observations:

A sliding window approach is particularly effective here since the windows overlap and share most of their characters with adjacent windows
When the window slides one position, only two characters change: one exits the window on the left, and one enters on the right
This observation enables an efficient O(n) solution instead of the naive O(n × k) approach

Example

Input

s = "abciiidef"
k = 3

Output

3

Explanation

We examine all substrings of length 3. The substring "iii" (at indices 3-5) contains 3 vowels, which is the maximum possible. Other substrings like "abc" contain 1 vowel ('a'), "bci" contains 1 vowel ('i'), "cii" contains 2 vowels, and so on.

Example

Input

s = "aeiou"
k = 2

Output

2

Explanation

Every character in the string is a vowel. Any window of size 2 will contain exactly 2 vowels. For instance, "ae", "ei", "io", and "ou" all have 2 vowels. Therefore, the maximum is 2.

Example

Input

s = "leetcode"
k = 3

Output

2

Explanation

Examining all windows of size 3: "lee" has 2 vowels ('e', 'e'), "eet" has 2 vowels ('e', 'e'), "etc" has 1 vowel ('e'), "tco" has 1 vowel ('o'), "cod" has 1 vowel ('o'), and "ode" has 2 vowels ('o', 'e'). The maximum vowel count among all windows is 2.

Accepted0/0·0% Acceptance

Constraints

1 ≤ s.length ≤ 10⁵
s consists exclusively of lowercase English letters (a-z)
1 ≤ k ≤ s.length

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

k =

s =

"abciiidef"

Loading problem...

101

00:00:00

Description

Editorial

Peak Vowel Count in Window

MEDIUM20 pts

A vowel in the English alphabet is defined as one of the following five characters: 'a', 'e', 'i', 'o', or 'u'.

You must scan through all possible contiguous windows of size k in the string and determine which window contains the highest concentration of vowels. Return this maximum count as an integer.

Key Observations:

A sliding window approach is particularly effective here since the windows overlap and share most of their characters with adjacent windows
When the window slides one position, only two characters change: one exits the window on the left, and one enters on the right
This observation enables an efficient O(n) solution instead of the naive O(n × k) approach

Example

Input

s = "abciiidef"
k = 3

Output

3

Explanation

Example

Input

s = "aeiou"
k = 2

Output

2

Explanation

Every character in the string is a vowel. Any window of size 2 will contain exactly 2 vowels. For instance, "ae", "ei", "io", and "ou" all have 2 vowels. Therefore, the maximum is 2.

Example

Input

s = "leetcode"
k = 3

Output

2

Explanation

Accepted0/0·0% Acceptance

Constraints

1 ≤ s.length ≤ 10⁵
s consists exclusively of lowercase English letters (a-z)
1 ≤ k ≤ s.length

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

k =

s =

"abciiidef"

Peak Vowel Count in Window

Hints

Peak Vowel Count in Window

Hints