Count anagrams having first character as a consonant and no pair of consonants or vowels placed adjacently

0 0 15 minutes read

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 not
function isConsonant(c) {
return (c !== 'A' && c !== 'E' && c !== 'I' && c !== 'O' && c !== 'U');
}
 
// function to swap two characters in a string at given positions
function 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 generated
if (l === r) {
let check = true;
// checking if the condition is satisfied or not
for (let i = 0; i < str.length; i++) {
if (i % 2 === 0) { // even indices should have a consonant
if (!isConsonant(str[i])) {
check = false;
break;
}
} else { // odd indices should have a vowel
if (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

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 C₁, C₂…, C_N consonants and V₁, V₂, …, V_N vowels in the string S and $\sum C$ and \sum C $\sum V$ denote the total number of consonants and vowels respectively, then the answer would be:

$\frac{\sum C! * \sum V!}{(\sum C_1! *\sum C_2! * ... *C_N!)*(\sum V_1! *\sum V_2! * ... *V_N!)}$

where,
C_i is the count of i^th consonant.
_Vi is the count of i^th 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 1000001
using namespace std;
 
// Function to compute factorials till N
void 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 not
bool 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 condition
void 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 Code
int 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 = 1000000007
N = 1000001
 
fac = {}
 
# Function to compute factorials till N
def 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 not
def 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 condition
def 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 Code
if __name__ == '__main__':
    S = "GADO"
    l = len(S)
    countAnagrams(S, l)
     
    # This code is contributed by ipg2016107.

C#

// C# program for the above approach
using 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 approach
 
const mod = 1000000007;
const N = 1000001;
 
let fac = {};
 
// Function to compute factorials till N
function 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 not
function 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 condition
function 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 Code
let S = "GADO";
let l = S.length;
 
countAnagrams(S, l);
 
 
// This code is contributed by phasing17

Output

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 zambiatek!