Count Vowel Strings With Follow Rules
Updated
Problem statement
Count the strings of length n that use only the lowercase vowels a, e, i, o and u and obey these rules about which letter may come right after each letter:
- After
a, the next letter must bee. - After
e, the next letter must beaori. - After
i, the next letter can be any vowel excepti. - After
o, the next letter must beioru. - After
u, the next letter must bea.
The first letter can be any vowel. The count can be very large, so return it modulo 10^9 + 7.
Function
countVowelStrings(n: int) → intExamples
Example 1
n = 3return = 19Group the valid strings by their last letter. For length 2 the counts are a: 3, e: 2, i: 2, o: 1, u: 2. A length-3 string ends in a if the letter before it is e, i or u, giving 2 + 2 + 2 = 6. In the same way it ends in e in 3 + 2 = 5 ways, in i in 2 + 1 = 3 ways, in o in 2 ways and in u in 2 + 1 = 3 ways. The total is 6 + 5 + 3 + 2 + 3 = 19.
Example 2
n = 4return = 35Starting from the length-3 counts a: 6, e: 5, i: 3, o: 2, u: 3, the length-4 counts are a: 5 + 3 + 3 = 11, e: 6 + 3 = 9, i: 5 + 2 = 7, o: 3 and u: 3 + 2 = 5. The total is 35.
Example 3
n = 40return = 196669546There are 503196673067 valid strings of length 40. That is more than 10^9 + 7, so the answer is 503196673067 modulo 10^9 + 7, which is 196669546.
Constraints
1 <= n <= 10^5
More C3.ai interview questions
- Drop Recent Duplicate MessagesOA · Seen Oct 2026
- Maximum K-Star SumOA · Seen Oct 2026
- Largest Square Sub-Grid Within a Sum LimitOA · Seen Jan 2023
- Prefix Scores With the Running MaximumOA · Seen Jan 2023
- Tree Node With Maximum BeautyOA · Seen Nov 2022
- Photo Album Insert OrderOA · Seen Apr 2022
- Sort by Frequency, Then ValueOA · Seen Apr 2022
- Count Distinct Binary Search TreesOA · Seen Mar 2022
- Count Palindromic Subsequences of Length KOA · Seen Mar 2022
- Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024
Similar questions at other companies
- String Transformation (Also for Infra Automation Intern)Snowflake · OASnowflake interview questions
- Sum of All ValuesFlexport · OAFlexport interview questions
- Without WhitespacesPostman · OAPostman interview questions
- Largest Minus Smallest Value of a Parenthesized ExpressionNutanix · ONSITE INTERVIEWNutanix interview questions
- Lexicographically Smallest Grid Path with One Letter ChangeInfosys · OAInfosys interview questions
- Minimum Merge ConflictsAmazon · OA
- Maximum Signal Walk in a Server TreeTower Research Capital · OA
- Balance a Chemical EquationMicrosoft · OAMicrosoft interview questions
- Binary CircuitAkuna Capital · OAAkuna Capital interview questions
- Jump Game with Prime-3 StepsUber · OAUber interview questions