Given a string S of length N, the task is to count the number of anagrams of S whose first character is a consonant and no pair of consonants or vowels are adjacent to each other.
Examples:
Input: S = “GADO”
Output: 4
Explanation:
The anagrams of string S satisfying the given conditions are GADO, GODA, DOGA, DAGO.
Therefore, the total number of such anagrams is 4.Input: S = “AABCY”
Output: 6
Explanation:
The anagrams of the string S satisfying the given conditions are BACAY, BAYAC, CABAY, CAYAB, YABAC, YACAB.
Therefore, the total number of such anagrams is 6.
Naive Approach: The simplest approach is to generate all possible anagrams of the given string and count those anagrams that satisfy the given condition. Finally, print the count obtained.
C++
#include <algorithm>#include <iostream>#include <string>using namespace std;// Checking for consonant.bool is_consonant(char c){ return (c != 'A' && c != 'E' && c != 'I' && c != 'O' && c != 'U');}// Generate all possible anagrams of s and count those// anagrams that satisfy the condition that the first// character is a consonant and no pair of consonants or// vowels placed adjacently i.e In other words at all even// index(starting with 0) there should be a consonant and// every odd index should be vowel.int countAnagrams(string s){ // Generate all permutations of the string s sort(s.begin(), s.end()); int count = 0; do { // Flag to check if condition is satisfied bool check = true; for (int i = 0; i < s.length(); i++) { // Check if at all even index there is consonant // or not. if (i % 2 == 0) { if (!is_consonant(s[i])) { check = false; break; } } // Check if at all odd index there is vowel // or not. else { if (is_consonant(s[i])) { check = false; break; } } } // Increase the count if condition satisfies if (check) count++; } while (next_permutation(s.begin(), s.end())); return count;}int main(){ string S = "GADO"; cout << countAnagrams(S) << endl; return 0;} |
Java
import java.util.Arrays;public class Main{ // Checking for consonant. static boolean is_consonant(char c) { return (c != 'A' && c != 'E' && c != 'I' && c != 'O' && c != 'U'); } // Generate all possible anagrams of s and count those // anagrams that satisfy the condition that the first // character is a consonant and no pair of consonants or // vowels placed adjacently i.e In other words at all // even index(starting with 0) there should be a // consonant and every odd index should be vowel. static int countAnagrams(String s) { // Generate all permutations of the string s char[] arr = s.toCharArray(); Arrays.sort(arr); int count = 0; do { // Flag to check if condition is satisfied boolean check = true; for (int i = 0; i < arr.length; i++) { // Check if at all even index there is // consonant or not. if (i % 2 == 0) { if (!is_consonant(arr[i])) { check = false; break; } } // Check if at all odd index there is vowel // or not. else { if (is_consonant(arr[i])) { check = false; break; } } } // Increase the count if condition satisfies if (check) count++; } while (nextPermutation(arr)); return count; } // Function to generate next permutation static boolean nextPermutation(char[] arr) { int n = arr.length; int i = n - 2; while (i >= 0 && arr[i] >= arr[i + 1]) { i--; } if (i < 0) { return false; } int j = n - 1; while (arr[j] <= arr[i]) { j--; } char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; Arrays.sort(arr, i + 1, n); return true; } // Driver Code public static void main(String[] args) { String S = "GADO"; System.out.println(countAnagrams(S)); }} |
Python3
from itertools import permutations# Checking for consonant.def is_consonant(c): return c not in "AEIOU"# Generate all possible anagrams of s and count those anagrams# that satisfy the condition that the first character is a consonant# and no pair of consonants or vowels placed adjacently# i.e In other words at all even index(starting with 0) there should # be a consonant and every odd index should be vowel. def countAnagrams(s): # Generate all permutations of the string s perms = permutations(s) # Count the anagrams that satisfy the condition count = 0 for perm in perms: # Flag to check if condition is satisfied check=1 for i in range(len(perm)): # Check if at all even index there is consonant # or not. if(i%2==0): if(not is_consonant(perm[i])): check=0 # Check if at all odd index there is vowel # or not. else: if(is_consonant(perm[i])): check=0 # Increase the count if condition satisfy if(check==1): count += 1 return count if __name__ == '__main__': S = "GADO" print(countAnagrams(S))# This code is contributed by Pushpesh Raj |
Javascript
// function to check whether a given character is a consonant or notfunction isConsonant(c) {return (c !== 'A' && c !== 'E' && c !== 'I' && c !== 'O' && c !== 'U');}// function to swap two characters in a string at given positionsfunction swap(str, i, j) {const temp = str[i];str = str.substring(0, i) + str[j] + str.substring(i+1);str = str.substring(0, j) + temp + str.substring(j+1);return str;}// function to generate all permutations of a given string and count those// anagrams that satisfy the condition that the first character is a consonant// and no pair of consonants or vowels placed adjacently, i.e., all even// indices should have a consonant and every odd index should have a vowel.function generatePermutations(str, l, r, count) {// base case: when all permutations have been generatedif (l === r) {let check = true;// checking if the condition is satisfied or notfor (let i = 0; i < str.length; i++) {if (i % 2 === 0) { // even indices should have a consonantif (!isConsonant(str[i])) {check = false;break;}} else { // odd indices should have a vowelif (isConsonant(str[i])) {check = false;break;}}}// increasing the count if the condition is satisfied if (check) { count[0]++; } } else { for (let i = l; i <= r; i++) { str = swap(str, l, i); generatePermutations(str, l+1, r, count); str = swap(str, l, i); } }}function countAnagrams(S) { let count = [0]; generatePermutations(S, 0, S.length-1, count); return count[0];}console.log(countAnagrams("GADO")); |
C#
using System;using System.Collections.Generic;using System.Linq;namespace ConsoleApp{ class Program { // Checking for consonant. static bool IsConsonant(char c) { return (c != 'A' && c != 'E' && c != 'I' && c != 'O' && c != 'U'); } // Generate all possible anagrams of s and count those // anagrams that satisfy the condition that the first // character is a consonant and no pair of consonants or // vowels placed adjacently i.e In other words at all even // index(starting with 0) there should be a consonant and // every odd index should be vowel. static int CountAnagrams(string s) { // Generate all permutations of the string s var permutations = GetPermutations(s); int count = 0; foreach (var permutation in permutations) { // Flag to check if condition is satisfied bool check = true; for (int i = 0; i < s.Length; i++) { // Check if at all even index there is consonant // or not. if (i % 2 == 0) { if (!IsConsonant(permutation[i])) { check = false; break; } } // Check if at all odd index there is vowel // or not. else { if (IsConsonant(permutation[i])) { check = false; break; } } } // Increase the count if condition satisfies if (check) count++; } return count; } // Get all permutations of a string static List<string> GetPermutations(string s) { var permutations = new List<string>(); GetPermutationsHelper(s.ToCharArray(), 0, permutations); return permutations; } static void GetPermutationsHelper(char[] s, int i, List<string> permutations) { if (i == s.Length - 1) { permutations.Add(new string(s)); } else { for (int j = i; j < s.Length; j++) { Swap(s, i, j); GetPermutationsHelper(s, i + 1, permutations); Swap(s, i, j); } } } static void Swap(char[] s, int i, int j) { char temp = s[i]; s[i] = s[j]; s[j] = temp; } static void Main(string[] args) { string S = "GADO"; Console.WriteLine(CountAnagrams(S)); } }} |
Output
4
Time Complexity: O(N!*N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized based on the following observations:
- Strings that have an equal number of consonants and vowels satisfy the given condition.
- Strings having one more consonant than vowel also satisfy the given condition.
- Apart from these two conditions, the count of possible anagrams will always be 0.
- Now, the problem can be solved by using a combinatorial formula. Consider there are C1, C2…, CN consonants and V1, V2, …, VN vowels in the string S and
and \sum C
denote the total number of consonants and vowels respectively, then the answer would be:
and \sum C
denote the total number of consonants and vowels respectively, then the answer would be:
where,
Ci is the count of ith consonant.
Vi is the count of ith vowel.
Follow the steps below to solve the problem:
- Initialize a variable, say answer, to store the total count of anagrams.
- Store the frequency of each character of the string S in a HashMap count.
- Store the number of vowels and consonants in S in variables V and C respectively.
- If the value of V is not equal to C or C is not equal to (V + 1), then print 0. Otherwise, performing the following steps:
- Initialize denominator as 1.
- Traverse the string S using the variable i and update the denominator as denominator*((count[S[i]])!).
- Initialize numerator to V!*C!, and update the value of answer as numerator/denominator.
- After completing the above steps, print the value of the answer as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#define ll long long#define mod 1000000007#define N 1000001using namespace std;// Function to compute factorials till Nvoid Precomputefact(unordered_map<ll, ll>& fac){ ll ans = 1; // Iterate in the range [1, N] for (ll i = 1; i <= N; i++) { // Update ans to ans*i ans = (ans * i) % mod; // Store the value of ans // in fac[i] fac[i] = ans; } return;}// Function to check whether the// current character is a vowel or notbool isVowel(char a){ if (a == 'A' || a == 'E' || a == 'I' || a == 'O' || a == 'U') return true; else return false;}// Function to count the number of// anagrams of S satisfying the// given conditionvoid countAnagrams(string s, int n){ // Store the factorials upto N unordered_map<ll, ll> fac; // Function Call to generate // all factorials upto n Precomputefact(fac); // Create a hashmap to store // frequencies of all characters unordered_map<char, ll> count; // Store the count of // vowels and consonants int vo = 0, co = 0; // Iterate through all // characters in the string for (int i = 0; i < n; i++) { // Update the frequency // of current character count[s[i]]++; // Check if the character // is vowel or consonant if (isVowel(s[i])) vo++; else co++; } // Check if ?C==?V+1 or ?C==?V if ((co == vo + 1) || (co == vo)) { // Store the denominator ll deno = 1; // Calculate the denominator // of the expression for (auto c : count) { // Multiply denominator by factorial // of counts of all letters deno = (deno * fac[c.second]) % mod; } // Store the numerator ll nume = fac[co] % mod; nume = (nume * fac[vo]) % mod; // Store the answer by dividing // numerator by denominator ll ans = nume / deno; // Print the answer cout << ans; } // Otherwise, print 0 else { cout << 0; }}// Driver Codeint main(){ string S = "GADO"; int l = S.size(); countAnagrams(S, l); return 0;} |
Java
import java.util.*;class Main { static int mod = 1000000007; static int N = 1000001; static HashMap<Integer, Long> fac = new HashMap<Integer, Long>(); // Function to compute factorials till N static void precomputeFact() { long ans = 1; // Iterate in the range [1, N] for (int i = 1; i <= N; i++) { // Update ans to ans*i ans = (ans * i) % mod; // Store the value of ans in fac[i] fac.put(i, ans); } } // Function to check whether the current character is a // vowel or not static boolean isVowel(char a) { return a == 'A' || a == 'E' || a == 'I' || a == 'O' || a == 'U'; } // Function to count the number of anagrams of S // satisfying the given condition static void countAnagrams(String s, int n) { // Store the factorials upto N // Function Call to generate all factorials upto n precomputeFact(); // Create a hashmap to store frequencies of all // characters HashMap<Character, Integer> count = new HashMap<>(); // Store the count of vowels and consonants int vo = 0; int co = 0; // Iterate through all characters in the string for (int i = 0; i < n; i++) { // Update the frequency of current character if (count.containsKey(s.charAt(i))) { count.put(s.charAt(i), count.get(s.charAt(i)) + 1); } else { count.put(s.charAt(i), 1); } // Check if the character is vowel or consonant if (isVowel(s.charAt(i))) { vo++; } else { co++; } } if (co == vo + 1 || co == vo) { // Store the denominator of the expression long deno = 1; // Calculate the denominator of the expression for (var item : count.entrySet()) { // Multiply denominator by factorial of // counts of all letters deno = (deno * fac.get(item.getValue())) % mod; } // Store the numerator long nume = fac.get(co) % mod; nume = (nume * fac.get(vo)) % mod; // Store the answer by dividing numerator by // denominator long ans = nume / deno; // Print the answer System.out.println(ans); } else { System.out.println(0); } } public static void main(String[] args) { String S = "GADO"; int l = S.length(); countAnagrams(S, l); }}// This code is contributed by phasing17. |
Python3
# Python 3 program for the above approach#include <bits/stdc++.h>mod = 1000000007N = 1000001fac = {}# Function to compute factorials till Ndef Precomputefact(): global fac ans = 1 # Iterate in the range [1, N] for i in range(1,N+1,1): # Update ans to ans*i ans = (ans * i) % mod # Store the value of ans # in fac[i] fac[i] = ans return# Function to check whether the# current character is a vowel or notdef isVowel(a): if (a == 'A' or a == 'E' or a == 'I' or a == 'O' or a == 'U'): return True else: return False# Function to count the number of# anagrams of S satisfying the# given conditiondef countAnagrams(s,n): # Store the factorials upto N global fac # Function Call to generate # all factorials upto n Precomputefact() # Create a hashmap to store # frequencies of all characters count = {} # Store the count of # vowels and consonants vo = 0 co = 0 # Iterate through all # characters in the string for i in range(n): # Update the frequency # of current character if s[i] in count: count[s[i]] += 1 else: count[s[i]] = 1 # Check if the character # is vowel or consonant if (isVowel(s[i])): vo += 1 else: co += 1 # Check if ?C==?V+1 or ?C==?V if ((co == vo + 1) or (co == vo)): # Store the denominator deno = 1 # Calculate the denominator # of the expression for key,value in count.items(): # Multiply denominator by factorial # of counts of all letters deno = (deno * fac[value]) % mod # Store the numerator nume = fac[co] % mod nume = (nume * fac[vo]) % mod # Store the answer by dividing # numerator by denominator ans = nume // deno # Print the answer print(ans) # Otherwise, print 0 else: print(0)# Driver Codeif __name__ == '__main__': S = "GADO" l = len(S) countAnagrams(S, l) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG { static int mod = 1000000007; static int N = 1000001; static Dictionary<int, long> fac = new Dictionary<int, long>(); // Function to compute factorials till N static void Precomputefact() { long ans = 1; // Iterate in the range [1, N] for (int i = 1; i <= N; i++) { // Update ans to ans*i ans = (ans * i) % mod; // Store the value of ans // in fac[i] fac[i] = ans; } } // Function to check whether the // current character is a vowel or not static bool IsVowel(char a) { return (a == 'A' || a == 'E' || a == 'I' || a == 'O' || a == 'U'); } // Function to count the number of // anagrams of S satisfying the // given condition static void CountAnagrams(string s, int n) { // Store the factorials upto N // Function Call to generate // all factorials upto n Precomputefact(); // Create a hashmap to store // frequencies of all characters Dictionary<char, int> count = new Dictionary<char, int>(); // Store the count of // vowels and consonants int vo = 0; int co = 0; // Iterate through all // characters in the string for (int i = 0; i < n; i++) { // Update the frequency // of current character if (count.ContainsKey(s[i])) { count[s[i]]++; } else { count[s[i]] = 1; } // Check if the character // is vowel or consonant if (IsVowel(s[i])) { vo++; } else { co++; } } // Check if ?C==?V+1 or ?C==?V if (co == vo + 1 || co == vo) { // Store the denominator long deno = 1; // Calculate the denominator // of the expression foreach(var item in count) { // Multiply denominator by factorial // of counts of all letters deno = (deno * fac[item.Value]) % mod; } // Store the numerator long nume = fac[co] % mod; nume = (nume * fac[vo]) % mod; // Store the answer by dividing // numerator by denominator long ans = nume / deno; // Print the answer Console.WriteLine(ans); } else Console.WriteLine(0); } public static void Main(string[] args) { string S = "GADO"; int l = S.Length; CountAnagrams(S, l); }}// This code is contributed by phasing17. |
Javascript
// JS program to implement the approachconst mod = 1000000007;const N = 1000001;let fac = {};// Function to compute factorials till Nfunction Precomputefact() { let ans = 1; // Iterate in the range [1, N] for (let i = 1; i <= N; i++) { // Update ans to ans*i ans = (ans * i) % mod; // Store the value of ans in fac[i] fac[i] = ans; } return;}// Function to check whether the current character is a vowel or notfunction isVowel(a) { if (a == "A" || a == "E" || a == "I" || a == "O" || a == "U") { return true; } else { return false; }}// Function to count the number of anagrams of S satisfying the given conditionfunction countAnagrams(s, n) { // Store the factorials upto N // Function Call to generate all factorials upto n Precomputefact(); // Create a hashmap to store frequencies of all characters let count = {}; // Store the count of vowels and consonants let vo = 0; let co = 0; // Iterate through all characters in the string for (let i = 0; i < n; i++) { // Update the frequency of current character if (s[i] in count) { count[s[i]] += 1; } else { count[s[i]] = 1; } // Check if the character is vowel or consonant if (isVowel(s[i])) { vo += 1; } else { co += 1; } } // Check if ?C==?V+1 or ?C==?V if (co == vo + 1 || co == vo) { // Store the denominator of the expression let deno = 1; // Calculate the denominator of the expression for (let key of Object.keys(count)) { // Multiply denominator by factorial of counts of all letters deno = (deno * fac[count[key]]) % mod; } // Store the numerator let nume = fac[co] % mod; nume = (nume * fac[vo]) % mod; // Store the answer by dividing numerator by denominator let ans = Math.floor(nume / deno); // Print the answer console.log(ans); } else { // Otherwise, print 0 console.log(0); }}// Driver Codelet S = "GADO";let l = S.length;countAnagrams(S, l);// This code is contributed by phasing17 |
Output
4
Time Complexity: O(N), The function Precomputefact() has a time complexity of O(N), as it iterates through all numbers from 1 to N and performs constant time operations.
The function countAnagrams() has a time complexity of O(N), as it iterates through all characters of the input string S and performs constant time operations.
The overall time complexity of the program is O(N), as the two functions are called one after the other.
Auxiliary Space: O(N), The function Precomputefact() stores all factorials up to N in an unordered_map, which has a space complexity of O(N).
The function countAnagrams() stores the frequencies of all characters in the input string S in an unordered_map, which has a space complexity of O(N).
The overall space complexity of the program is O(N), as the two unordered_maps are the only significant data structures used in the program.
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!
