String Patterns (Also for Core/Database Intern :)
Problem statement
Given the length of a word (wordLen) and the maximum number of consecutive vowels that it can
contain (maxVowels), determine how many unique words can be generated. Words will consist of
English alphabetic letters a through z only. Vowels are a, e, i, o, u; consonants
are the remaining 21 letters. In the explanations, v and c represent vowels and consonants.
Function
calculateWays(wordLen: int, maxVowels: int) → int
Complete the function calculateWays in the editor below.
calculateWays has the following parameters:
- 1.
int wordLen: the length of a word - 2.
int maxVowels: the maximum number of consecutive vowels allowed in a word
Returns
int: the number of well-formed strings that can be created, modulo 1000000007(109+7)
The result may be very large number, so return the answer modulo (109 + 7).
Note:
While the answers will be within the limit of a 32 bit integer, interim values may exceed that limit. Within the function, you may need to use a 64 bit integer type to store them.
Examples
Example 1
wordLen = 1maxVowels = 1return = 26
Patterns: {v, c} That means there are 26 possibilities, one for each letter in the alphabet.
Example 2
wordLen = 4maxVowels = 1return = 412776
Patterns: {cccc, vccc, cvcc, ccvc, cccv, cvcv, ccvv, vcvv, vvcc, vvcv} There are 412,776 possibilities - see above 👆: (21 * 21 * 21 * 21) = 194481 (5 * 21 * 21 * 21) + (21 * 5 * 21 * 21) + (21 * 21 * 5 * 21) + (21 * 21 * 21 * 5) = 4 * 46305 = 185220 (5 * 21 * 5 * 21) + (21 * 5 * 21 * 5) + (5 * 21 * 21 * 5) = 3 * 11025 = 33075 194481 + 185220 + 33075 = 412776 possible solutions.
Example 3
wordLen = 4maxVowels = 2return = 451101In this case, all of the combinations from the previous example are still valid. - There are 5 additional patterns to consider, three with 2 vowels (vvcc, cvvc, ccvv) and 2 with 3 vowels (vvcv and vcvv). - Their counts are 3 * (5 * 5 * 21 * 21) = 3 * 11025 = 33075 and 2 * (5 * 5 * 5 * 21) = 2 * 2625 = 5250. - The total number of combinations then is 412776 + 33075 + 5250 = 451101.
Constraints
- 1 ≤ wordLen ≤ 2500
- 0 ≤ maxVowels ≤ n