Given a string str and two integers P and Q. The task is to find the total count of words that can be formed by choosing exactly P consonants and Q vowels from the given string.
Examples:
Input: str = “geek”, P = 1, Q = 1
Output: 8
“ge”, “ge”, “eg”, “ek”, “eg”, “ek”,
“ke” and “ke” are the possible words.
Input: str = “crackathon”, P = 4, Q = 3
Output: 176400
Approach: Since P consonants and Q vowels has to be chosen from the original count of consonants and vowels in the given string. So, binomial coefficient can be used to calculate the combinations of choosing these characters and the characters chosen can be arranged in themselves using the factorial of their count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define lli long long int// Function to return the value of nCklli binomialCoeff(lli n, lli k){ if (k == 0 || k == n) return 1; return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k);}// Function to return the factorial of nlli fact(lli n){ if (n >= 1) return n * fact(n - 1); else return 1;}// Function that returns true if ch is a vowelbool isVowel(char ch){ if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { return true; } return false;}// Function to return the number of words possiblelli countWords(string s, int p, int q){ // To store the count of vowels and // consonanats in the given string lli countc = 0, countv = 0; for (int i = 0; i < s.length(); i++) { // If current character is a vowel if (isVowel(s[i])) countv++; else countc++; } // Find the total possible words lli a = binomialCoeff(countc, p); lli b = binomialCoeff(countv, q); lli c = fact(p + q); lli ans = (a * b) * c; return ans;}// Driver codeint main(){ string s = "crackathon"; int p = 4, q = 3; cout << countWords(s, p, q); return 0;} |
Java
// Java implementation of the above approach class GFG{ // Function to return the value of nCk static long binomialCoeff(long n, long k) { if (k == 0 || k == n) return 1; return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k); } // Function to return the factorial of n static long fact(long n) { if (n >= 1) return n * fact(n - 1); else return 1; } // Function that returns true if ch is a vowel static boolean isVowel(char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { return true; } return false; } // Function to return the number of words possible static long countWords(String s, int p, int q) { // To store the count of vowels and // consonanats in the given string long countc = 0, countv = 0; for (int i = 0; i < s.length(); i++) { // If current character is a vowel if (isVowel(s.charAt(i))) countv++; else countc++; } // Find the total possible words long a = binomialCoeff(countc, p); long b = binomialCoeff(countv, q); long c = fact(p + q); long ans = (a * b) * c; return ans; } // Driver code public static void main (String[] args) { String s = "crackathon"; int p = 4, q = 3; System.out.println(countWords(s, p, q)); } }// This Code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach# Function to return the value of nCkdef binomialCoeff(n, k): if (k == 0 or k == n): return 1 return binomialCoeff(n - 1, k - 1) + \ binomialCoeff(n - 1, k)# Function to return the factorial of ndef fact(n): if (n >= 1): return n * fact(n - 1) else: return 1# Function that returns true if ch is a voweldef isVowel(ch): if (ch == 'a' or ch == 'e' or ch == 'i' or ch == 'o' or ch == 'u'): return True return False# Function to return the number of words possibledef countWords(s, p, q): # To store the count of vowels and # consonanats in the given string countc = 0 countv = 0 for i in range(len(s)): # If current character is a vowel if (isVowel(s[i])): countv += 1 else: countc += 1 # Find the total possible words a = binomialCoeff(countc, p) b = binomialCoeff(countv, q) c = fact(p + q) ans = (a * b) * c return ans# Driver codes = "crackathon"p = 4q = 3print(countWords(s, p, q))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG{ // Function to return the value of nCk static long binomialCoeff(long n, long k) { if (k == 0 || k == n) return 1; return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k); } // Function to return the factorial of n static long fact(long n) { if (n >= 1) return n * fact(n - 1); else return 1; } // Function that returns true if ch is a vowel static bool isVowel(char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { return true; } return false; } // Function to return the number of words possible static long countWords(String s, int p, int q) { // To store the count of vowels and // consonanats in the given string long countc = 0, countv = 0; for (int i = 0; i < s.Length; i++) { // If current character is a vowel if (isVowel(s[i])) countv++; else countc++; } // Find the total possible words long a = binomialCoeff(countc, p); long b = binomialCoeff(countv, q); long c = fact(p + q); long ans = (a * b) * c; return ans; } // Driver code public static void Main (String[] args) { String s = "crackathon"; int p = 4, q = 3; Console.WriteLine(countWords(s, p, q)); } }// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript implementation of the approach// Function to return the value of nCkfunction binomialCoeff(n, k){ if (k == 0 || k == n) return 1; return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k);}// Function to return the factorial of nfunction fact(n){ if (n >= 1) return n * fact(n - 1); else return 1;}// Function that returns true if ch is a vowelfunction isVowel(ch){ if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { return true; } return false;}// Function to return the number of words possiblefunction countWords(s, p, q){ // To store the count of vowels and // consonanats in the given string var countc = 0, countv = 0; for (var i = 0; i < s.length; i++) { // If current character is a vowel if (isVowel(s[i])) countv++; else countc++; } // Find the total possible words var a = binomialCoeff(countc, p); var b = binomialCoeff(countv, q); var c = fact(p + q); var ans = (a * b) * c; return ans;}// Driver codevar s = "crackathon";var p = 4, q = 3;document.write(countWords(s, p, q));</script> |
Output:
176400
Time Complexity: O(2n)
Auxiliary Space: O(n)
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!
