PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Lavish Gupta
Tester: Abhinav Sharma, Utkarsh Gupta
Editorialist: Pratiyush Mishra
DIFFICULTY:
1241
PREREQUISITES:
None
PROBLEM:
Chef considers a string consisting of lowercase English alphabet beautiful if all the characters of the string are vowels.
Chef has a string S consisting of lowercase English alphabet, of length N. He wants to convert S into a beautiful string T. In order to do so, Chef does the following operation on every character of the string:
- If the character is a consonant, change the character to its closest vowel.
- If the character is a vowel, don’t change it.
Chef realizes that the final string T is not unique. Chef wonders, what is the total number of distinct beautiful strings T that can be obtained by performing the given operations on the string S.
Since the answer can be huge, print it modulo 10^9 + 7.
Note:
- There are 26 characters in the English alphabet. Five of these characters are vowels:
a
,e
,i
,o
, andu
. The remaining 21 characters are consonants. - The closest vowel to a consonant is the vowel that is at least distant from that consonant. For example, the distance between the characters
d
ande
is 1 while the distance between the charactersd
anda
is 3. - The distance between the characters
z
anda
is 25 and not 1.
EXPLANATION:
In this problem we need to change all the consonants to their nearest vowel. The consonants that have a unique vowel nearest to it will just have one choice, that is to change into that vowel, however for vowels that have 2 vowels at same closest distance, it will have 2 choices. Thus we just need to calculate all consonants that have 2 choices. Let us denote this by count. Then our final answer would be:
TIME COMPLEXITY:
O(N), for each test case.
SOLUTION:
Editorialist’s Solution
Tester1’s Solution
Tester2’s Solution