Count Vowels

Q: What is the time complexity of counting vowels?

O(n) , where n is the length of the string, because each character is checked once against at most five letters. The extra space is O(1) : one counter and the fixed set of vowels.

Q: Is y a vowel in this problem?

No. In English spelling y sometimes acts as a vowel, as in rhythm , but programming problems almost always define the vowels as a , e , i , o and u , and this one does. If a problem includes y , add it to the letters you check.

BeginnerArrays and strings

+10

Given a string s of English letters, return how many of its characters are vowels. The vowels are a, e, i, o and u, in lower or upper case. The letter y does not count.

Function

countVowels(s: string) → integer

sstring: the string of English letters to scan
Returnsinteger: the number of vowels in s, upper and lower case together

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s contains only English letters (a to z, A to Z).

Examples

Input: s = "Interview"
Output: 4
Explanation: The vowels are I, e, i and e. The capital I counts like a lower case one, so the answer is 4.

Input: s = "rhythm"
Output: 0
Explanation: rhythm has no a, e, i, o or u, and y is not on the list, so the answer is 0.

Follow-up

Can you return how many times each of the five vowels appears, still reading the string only once?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Read the string once with a counter. Fold each character to lower case, so one check against the five vowels covers both cases.

Count each vowel with its own pass

Intuition

Count each of the ten letters in aeiouAEIOU with its own pass over the string, then add the ten counts. Every vowel equals exactly one of the ten letters, so it is counted once, and no consonant equals any of them.

The string is read ten times. That is still O(n), but for 5 × 10^4 characters it means 5 × 10^5 comparisons where one pass reads each character once.

Algorithm

Set total = 0.
Take the ten letters aeiouAEIOU one at a time.
For each letter, walk the whole string and add 1 to total every time a character equals it.
After the ten passes, return total.

def countVowels(s):
    total = 0
    for vowel in "aeiouAEIOU":
        total += s.count(vowel)  # one pass over s for this letter
    return total

One pass with a lower case check

Intuition

Read the string once and ask of each character whether it is a vowel. Converting it to lower case first turns I into i and leaves consonants as consonants, so you compare against five letters instead of ten.

The check takes constant time: a switch, a set lookup, or a search in the string aeiou. Each character is read once and only a counter is stored: O(n) time, O(1) space.

Algorithm

Set count = 0.
Walk the string one character at a time.
Convert the character to lower case.
If it is a, e, i, o or u, add 1 to count.
Return count.

def countVowels(s):
    vowels = set("aeiou")
    count = 0
    for ch in s:
        if ch.lower() in vowels:
            count += 1
    return count

Pitfalls and edge cases

Checking only lower case. Comparing against aeiou alone misses the capital I in Interview and returns 3.
Counting y. Here it is never a vowel, so rhythm gives 0.
Treating index 0 as a miss. "aeiou".indexOf('a') is 0, which is a match. Test for -1, or in PHP compare strpos with false using !==, because 0 == false there.
Calling strlen(s) in the loop condition in C. It rescans the string on every step, so 5 × 10^4 characters cost about 2.5 × 10^9 steps.

Frequently asked questions3

How do you count the vowels in a string?

Walk the string once with a counter. Convert each character to lower case and add 1 if it is a, e, i, o or u. When the loop ends, the counter holds the answer.

What is the time complexity of counting vowels?

O(n), where n is the length of the string, because each character is checked once against at most five letters. The extra space is O(1): one counter and the fixed set of vowels.

Is y a vowel in this problem?

No. In English spelling y sometimes acts as a vowel, as in rhythm, but programming problems almost always define the vowels as a, e, i, o and u, and this one does. If a problem includes y, add it to the letters you check.

def countVowels(s):
    # Write code here

Test #1

Test #2

Argument

s = "Interview"

Expected Output