Short Vowels
InterviewTime limit1sMemory limit1024 MB
Count the subsequences of a word (not the whole word, not empty) that contain no short vowel, meaning no vowel followed by two or more consonants.
- Level
Medium7 of 10
- Topics
- Dynamic programming, String, Combinatorics, Implementation
- Solved
- No attempts yet
Problem
Solving algorithm problems is hard, but one thing that is often even harder is preparing the test data. Take the problem Arabiska for example. There, the jury spent many hours of intense work constructing masterpieces like hej vad heter du.
A question that comes up is: how do you create strings that contain no short vowels? If you read the Arabiska problem, you may remember that a short vowel is a vowel followed by at least two consonants. In the word tall, the a is a short vowel, while the word potatis has no short vowels. For simplicity, we count a, e, i, o, u, y as vowels in this problem.
One way to create words with no short vowels is to start from a word and then remove some letters from it. Starting from potatis, we could for example get ptais. But if the word instead became otats, a short vowel appeared.
Your task is to count the number of ways to remove letters from a given word so that the result contains no short vowels. It is allowed to remove no letters at all (in the second example this contributes to the answer). It is not allowed to remove all letters, however. If the same word arises by removing different sets of letters, they are counted separately (in the first example there are two ways to get the word tal: we can remove the first or the second l).
Input
The input consists of one line with a word of at most letters. The word consists only of the letters a-z.
Output
Print an integer, the number of ways to remove letters so that a word with no short vowels is formed.
Note that the answer does not always fit in a -bit integer.