Count of possible Strings by replacing consonants with nearest vowel

Improve Article

Save Article

Like Article

Given a string str consisting of N letters, the task is to find the total number of strings that can be generated by replacing each consonant with the vowel closest to it in the English alphabet.

Examples:

Input: str = “code”
Output: 2
Explanation: Str = “code” has two consonant c and d. 
Closest vowel to d is e and closest to c are a and e.
The possible strings are “aoee” and “eoee“

Input: str = “geeks”
Output: 2

Approach: The problem can be solved based on the following observation:

There are total 21 consonant in which ‘c’, ‘g’, ‘l’ and ‘r’ are consonant which is closest to two vowels. 
So only these consonants have 2 choices and the reamining have one choices each.
Therefore, the total number of possible strings = the product of the number of choices for each consonant.

Follow the steps mentioned below to implement the observation:

  • Initialize a variable (say res = 1) to store the number of possible strings.
  • Iterate through the string from i = 0 to N:
    • If the character is one of the four special consonants mentioned above then they have two choices. So multiply 2 with res.
    • Otherwise, multiply 1 with the value of res.
  • The final value of res is the required answer.

Below is the implementation of the above approach:

C++

  

#include <bits/stdc++.h>

using namespace std;

  

int uniqueString(string str)

{

    long long int res = 1;

    for (int i = 0; i < str.length(); i++) {

        if (str[i] == 'c' || str[i] == 'g'

            || str[i] == 'l' || str[i] == 'r') {

            res = res * 2;

        }

    }

  

    

    

    return res;

}

  

int main()

{

    string str = "code";

  

    

    cout << (uniqueString(str));

    return 0;

}

Java

  

import java.io.*;

  

class GFG {

    

    public static int beautyString(String str)

    {

        char alpha[]

            = str.toCharArray();

        

        int res = 1, count = 0;

        

        for (int i = 0; i < str.length(); i++) {

            if (alpha[i] == 'c' || alpha[i] == 'g'

                || alpha[i] == 'l' || alpha[i] == 'r') {

                count++;

                res = res * 2;

            }

        }

        return res;

    }

    

    public static void main(String[] args)

    {

        String str = "code";

        

        System.out.println(beautyString(str));

    }

}

Time Complexity: O(N)
Auxiliary Space: O(1)

By Julio MarchiPosted on