 # CLOSEVOWEL Editorial

Setter: Lavish Gupta
Tester: Abhinav Sharma, Utkarsh Gupta
Editorialist: Pratiyush Mishra

1241

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`, and `u`. 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` and `e` is 1 while the distance between the characters `d` and `a` is 3.
• The distance between the characters `z` and `a` 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:

my solution:

``````for _ in range(int(input())):
N = int(input())
s = input()
equi = ['c','g','l','r']
ans = 0
for i in s:
if i in equi: ans += 1
print((2**ans)%1000000007)
``````
2 Likes