CLOSEVOWEL Editorial

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, 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:

answer = 2^{count}

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

Editorialist’s Solution
Tester1’s Solution
Tester2’s 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