Count strings with consonants and vowels at alternate position

0 0 5 minutes read

Given a string str. The task is to find all possible number of strings that can be obtained by replacing the “$” with alphabets in the given string.

Note: Alphabets should be placed in such a way that the string is always alternating in vowels and consonants, and the string must always start with a consonant. It is assumed that such a string is always possible, i.e. there is no need to care about the characters other than “$”.

Examples:

Input: str = "y$s"
Output: 5
$ can be replaced with any of the 5 vowels.
So, there can be 5 strings.

Input: str = "s$$e$"
Output 2205

Approach: It is given that the string will start with a consonant. So, if ‘$’ is at even position(considering 0-based indexing) then there should be a consonant else there should be a vowel. Also, given that there is no need to care about the characters other than “$”, i.e., characters other than “$” are placed correctly in the string maintaining the alternating consonant and vowel sequence. Let us understand the problem with an example.

str = “s$$e$”
Here we have to find the number of ways to form a string with given constraints.

First occurrence of $ is at 2nd position i.e. 1st index, so we can use 5 vowels.

Second occurrence of $ is at 3rd position, so we can use 21 consonants.

Third occurrence of $ is at 5th position, so we can use 21 consonants.

So, total number of ways to form above string is = 5*21*21 = 2205

Below is the implementation of the above approach:

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the count of strings
int countStrings(string s)
{
    // Variable to store the final result
    long sum = 1;
 
    // Loop iterating through string
    for (int i = 0; i < s.size(); i++) {
 
        // If '$' is present at the even
        // position in the string
        if (i % 2 == 0 && s[i] == '$')
 
            //'sum' is multiplied by 21
            sum *= 21;
 
        // If '$' is present at the odd
        // position in the string
        else if (s[i] == '$')
 
            //'sum' is multiplied by 5
            sum *= 5;
    }
 
    return sum;
}
 
// Driver code
int main()
{
    // Let the string 'str' be s$$e$
    string str = "s$$e$";
 
    // Print result
    cout << countStrings(str) << endl;
    return 0;
}

Java

// Java implementation of above approach
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG{
 
// Function to find the count of strings
static int countStrings(String s)
{
    // Variable to store the final result
    int sum = 1;
  
    // Loop iterating through string
    for (int i = 0; i < s.length(); i++) {
  
        // If '$' is present at the even
        // position in the string
        if (i % 2 == 0 && s.charAt(i) == '$')
  
            //'sum' is multiplied by 21
            sum *= 21;
  
        // If '$' is present at the odd
        // position in the string
        else if (s.charAt(i) == '$')
  
            //'sum' is multiplied by 5
            sum *= 5;
    }
  
    return sum;
}
  
// Driver code
public static void main(String args[])
{
    // Let the string 'str' be s$$e$
    String str = "s$$e$";
  
    // Print result
    System.out.println(countStrings(str));
}
}

Python 3

# Python 3 implementation of above approach
 
# Function to find the count of strings
def countStrings(s):
     
    # Variable to store the final result
    sum = 1
 
    # Loop iterating through string
    for i in range(len(s)):
 
        # If '$' is present at the even
        # position in the string
        if (i % 2 == 0 and s[i] == '$'):
 
            #'sum' is multiplied by 21
            sum *= 21
 
        # If '$' is present at the odd
        # position in the string
        elif(s[i] == '$'):
 
            # 'sum' is multiplied by 5
            sum *= 5
 
    return sum
 
# Driver code
if __name__ == "__main__":
     
    # Let the string 'str' be s$$e$
    str = "s$$e$"
 
    # Print result
    print(countStrings(str))
     
# this code is contributed by ChitraNayal

C#

// C# implementation of above approach
 
using System;
 
class GFG{
  
// Function to find the count of strings
static int countStrings(String s)
{
    // Variable to store the final result
    int sum = 1;
   
    // Loop iterating through string
    for (int i = 0; i < s.Length; i++) {
   
        // If '$' is present at the even
        // position in the string
        if (i % 2 == 0 && s[i] == '$')
   
            //'sum' is multiplied by 21
            sum *= 21;
   
        // If '$' is present at the odd
        // position in the string
        else if (s[i] == '$')
   
            //'sum' is multiplied by 5
            sum *= 5;
    }
   
    return sum;
}
   
// Driver code
public static void Main()
{
    // Let the string 'str' be s$$e$
    String str = "s$$e$";
   
    // Print result
    Console.WriteLine(countStrings(str));
}
}

PHP

<?php
// PHP implementation of above approach 
 
// Function to find the count of strings 
function countStrings($s) 
{ 
    // Variable to store the 
    // final result 
    $sum = 1; 
 
    // Loop iterating through string 
    for ($i = 0; $i < strlen($s); $i++) 
    { 
 
        // If '$' is present at the even 
        // position in the string 
        if ($i % 2 == 0 && $s[$i] == '$') 
 
            //'sum' is multiplied by 21 
            $sum *= 21; 
 
        // If '$' is present at the odd 
        // position in the string 
        else if ($s[$i] == '$') 
 
            //'sum' is multiplied by 5 
            $sum *= 5; 
    } 
 
    return $sum; 
} 
 
// Driver code 
 
// Let the string 'str' be s$$e$ 
$str = "s\$\$e\$"; 
 
// Print result 
echo countStrings($str);
 
// This code is contributed by Ryuga
?>

Javascript

<script>
// javascript implementation of above approach
 
// Function to find the count of strings
function countStrings( s)
{
 
    // Variable to store the final result
    let sum = 1;
 
    // Loop iterating through string
    for (let i = 0; i < s.length; i++)
    {
 
        // If '$' is present at the even
        // position in the string
        if (i % 2 == 0 && s[i] == '$')
 
            //'sum' is multiplied by 21
            sum *= 21;
 
        // If '$' is present at the odd
        // position in the string
        else if (s[i] == '$')
 
            //'sum' is multiplied by 5
            sum *= 5;
    }
    return sum;
}
 
// Driver code
 
    // Let the string 'str' be s$$e$
    let str = "s$$e$";
 
    // Print result
    document.write(countStrings(str));
     
// This code is contributed by gauravrajput1
</script>

Output

Time complexity: O(n) where n is length of given string

Auxiliary space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!