Given a string S consisting of lowercase English alphabets, of length N, the task is to find the total number of distinct strings that can be obtained by performing the given operations on every character of the string S:
- If the character is a consonant, change the character to its closest vowel.
- If the character is a vowel, change the character to its closest consonant.
Note: Do not take distance circularly, so, the distance between the characters a and z is 25 and not 1.
Examples:
Input: S = “face”
Output: 4
Explanation: for ‘f’ closest vowel is ‘e’,
for ‘a’ closest consonant is ‘b’,
for ‘c’ closest vowel is ‘a’ and ‘e’,
for ‘e’ closest consonant is ‘d’ and ‘f’,
So, total distinct strings are 2 * 2 = 4, i.e., “ebad”, “ebaf”, “ebed”, “ebef”.Input: S = “unique”
Output: 16
Approach: To solve the problem follow the below idea:
- Each vowel except a has two consonants closest to it which are just the previous letter and just the next letter in the English alphabet. So for every vowel there are two choices.
- Each consonant has only 1 vowel closest to it except for ‘c’, ‘g’, ‘l’ and ‘r’ which have two vowels in same distance. So for those there are two choices and all other consonants have only one choice.
Therefore, from the theory of counting, we can say the total number of choices equal to the product of choices for each consonant and each vowel present in the string.
Follow the below steps to solve the problem:
- Initialize the count of distinct strings = 1.
- Run a loop in the string and check,
- If the current character is a vowel then multiply the count by 2 if it is not ‘a’.
- If the current character is a consonant and one among ‘c’, ‘g’, ‘l’ and ‘r’, then multiply the final count by 2.
- The final count after the iteration is over is the required answer.
Below is the implementation of the above approach:
C++
|
|
Time Complexity: O(N)
Auxiliary Space: O(1)