Closest Vowels codechef solution in c++

 

Chef considers a string consisting of lowercase English alphabets beautiful if all the characters of the string are vowels.

Chef has a string S$S$ consisting of lowercase English alphabets, of length N$N$. He wants to convert S$S$ into a beautiful string T$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$T$ is not unique. Chef wonders, what is the total number of distinct beautiful strings T$T$ that can be obtained by performing the given operations on the string S$S$.

Since the answer can be huge, print it modulo 109+7${10}^9+7$.

Note:

• There are 26$26$ characters in the English alphabet. Five of these characters are vowels: a, e, i, o, and u. The remaining 21$21$ characters are consonants.
• The closest vowel to a consonant is the vowel that is least distant from that consonant. For example, the distance between the characters d and e is 1$1$ while the distance between the characters d and a is 3$3$.
• The distance between the characters z and a is 25$25$ and not 1$1$.

Input Format

• The first line of input will contain an integer T$T$ — the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains an integer N$N$, denoting the length of the string S$S$.
• The second line of each test case contains a string S$S$ consisting of lowercase English alphabets.

Output Format

For each test case, output the total number of distinct beautiful strings T$T$ that can be obtained by performing the given operations on the string S$S$, modulo 109+7${10}^9+7$.

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 1≤N≤105$1\le N\le {10}^5$
• Sum of N$N$ over all test cases does not exceed 105${10}^5$.

Sample Input 1 

4
5
aeiou
5
abcde
8
starters
8
codechef

Sample Output 1 

1
2
4
4

Explanation

Test case 1$1$: All the characters of the string S$S$ are vowels. Thus, none of the characters would be changed. The resulting string T$T$ will be aeiou.

Test case 2$2$:There are 2$2$ possible strings that can be obtained by performing the given operations on the string S$S$. Those are aaaee and aaeee.

solution in cpp

2. #include<iostream>
3. #define ll long long
4. #include<vector>
5. #include<stack>
6. #include<string>
7. #include<algorithm>
8. using namespace std;
9. 
   
10. void solve()
11. {
12. ll n;
13. cin >> n;
14. string s;
15. cin >> s;
16. ll ans = 1;
17. const int m= 1e9 + 7;
18. for (ll i = 0; i < n; i++)
19. {
20. if (s[i] == 'c' || s[i] == 'g' || s[i] == 'l' || s[i] == 'r')
21. ans = (ans * 2) % m;
22. }
23. cout << ans << "\n";
24. }
25. 
    
26. int main()
27. {
28. int t;
29. cin >> t;
30. while (t--)
31. {
32. solve();
33. }
34. return 0;
35. }