Vowel String Limit
MediumDynamic Programming · Snowflake
Count the strings of length n over the 26 lowercase English letters in which no more than k vowels appear in a row.
The vowels are a, e, i, o, u (5 letters); the other 21 letters are consonants. A string is valid when every maximal block of consecutive vowels has length at most k. With k = 0, vowels are not allowed at all.
Return the number of valid strings modulo 10^9 + 7. For n = 0, the only string is the empty string, which is valid.
Example 1
- Input:
- n = 2, k = 1
- Output:
- 651
- Explanation
- Of the 26 * 26 = 676 strings of length 2, the only invalid ones are vowel followed by vowel, of which there are 5 * 5 = 25. That leaves 676 - 25 = 651.
Example 2
- Input:
- n = 3, k = 1
- Output:
- 16401
- Explanation
- Of the 263 = 17576 strings, the bad ones have a vowel pair at positions 0-1 or 1-2. Each case has 25 * 26 = 650 strings and 125 strings have both, so 650 + 650 - 125 = 1175 are removed, leaving 16401.
Example 3
- Input:
- n = 3, k = 0
- Output:
- 9261
- Explanation
- With
k = 0every position must be a consonant, so the count is 213 = 9261.
Constraints
0 <= n <= 10^50 <= k <= n