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 stringsint 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 codeint 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 approachimport java.util.*;import java.lang.*;import java.io.*;class GFG{// Function to find the count of stringsstatic 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 codepublic 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 stringsdef 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 codeif __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 approachusing System;class GFG{ // Function to find the count of stringsstatic 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 codepublic 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 stringsfunction 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
2205
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
