Count Vowels

Q: What is the time complexity of counting vowels?

It is O(n) , where n is the length of the string, because each character is checked once and each check compares 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

You get a string s made of English letters. Count how many of its characters are vowels and return that number. 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 the same as a lower case one, so the answer is 4.

Input: s = "rhythm"
Output: 0
Explanation: rhythm has no a, e, i, o or u. Its y sounds like a vowel, but it is not on the list, so the answer is 0.

+18 hidden tests on Submit

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

Counting takes one pass over the string with a counter. The only decisions are how to test whether a character is a vowel and what to do with upper case. Fold each character to lower case and compare it against the five vowels, and every character costs a constant amount of work.

Count each vowel with its own pass

Intuition

Break the question into ten smaller ones: how many as are there, how many es, and so on through U. Each of those is a plain count. Walk the string and add 1 whenever the character equals the letter you are looking for, then add the ten counts together.

Every vowel in s equals exactly one of the ten letters in aeiouAEIOU, so it is counted exactly once, and no consonant equals any of them. For Interview, the pass for e finds 2, the pass for i finds 1, the pass for I finds 1, and the other seven passes find nothing: 4 in total.

The string is read ten times, about 10n comparisons. That is still O(n), because ten is a constant, but for 5 × 10^4 characters it means 5 × 10^5 comparisons where one pass would read 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

Turn the loops around. Read the string once, and for each character ask one question: is it a vowel? To cover both cases with a single check, convert the character to lower case first. I becomes i and E becomes e, while consonants stay consonants, so you only compare against the five letters a, e, i, o and u.

The check takes constant time: a switch over five letters, a lookup in a set, or a search in the five-letter string aeiou. Walking Interview, the counter goes up at I, e, i and e, and ends at 4.

Every character is read once, so the time is O(n). The memory is the counter and the five vowels, 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

The task fits in a few lines, and the misses come from cases the first check forgets.

Checking only lower case. Comparing against aeiou alone misses the capital I in Interview and returns 3. Fold the character to lower case, or list all ten letters.
Counting y. In this problem y 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 walks the whole string on every iteration, so 5 × 10^4 characters cost about 2.5 × 10^9 steps. Stop at the '\0' terminator, or compute the length once before the loop.

Frequently asked questions4

How do you count the vowels in a string?

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

What is the time complexity of counting vowels?

It is O(n), where n is the length of the string, because each character is checked once and each check compares 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.

Should the vowel check use a set, a switch or a string search?

With five letters, all three take constant time per character, and the speed difference between them is too small to matter. Pick the one that reads best in your language: a switch in C, C++ or Go, a set or a string search in Python, JavaScript or Ruby.

Python

def countVowels(s):
    # Write code here

Test cases

Case 1

Case 2

Input

s = "Interview"

Expected