Skip to content

Instantly share code, notes, and snippets.

@nayyaung
Last active May 2, 2022 14:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nayyaung/d9445d4fa3b6914bd642e583e23a391a to your computer and use it in GitHub Desktop.
Save nayyaung/d9445d4fa3b6914bd642e583e23a391a to your computer and use it in GitHub Desktop.
Count anagram that starts with consonant and has no consecutive vowels
package com.example;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class AnagramWithAlternateVowel_3 {
private final int mod = 1000000007;
private HashMap<Integer, Integer> factMap;
private void computeFactorial(int n) {
factMap = new HashMap<>();
int result = 1;
factMap.put(0, 1);
factMap.put(1, 1);
for (int i = 2; i <= n; i++) {
result = (result * i) % mod;
factMap.put(i, result);
}
}
private boolean isVowel(char c) {
return Arrays.asList('A', 'E', 'I', 'O', 'U').contains(c);
}
public int getCount(String s) {
int len = s.length();
computeFactorial(len);
int cCount = 0, vCount = 0;
HashMap<Character, Integer> cMap = new HashMap<>();
HashMap<Character, Integer> vMap = new HashMap<>();
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
if (isVowel(c)) {
vCount++;
vMap.put(c, vMap.getOrDefault(c, 0) + 1);
} else {
cCount++;
cMap.put(c, cMap.getOrDefault(c, 0) + 1);
}
}
if (cCount != vCount && cCount != vCount + 1) {
return 0;
}
// Permutation of all consonants = cCount!/(cCount - cCountToBeUsed)! => cCount!
// Duplicate of consonants cCountOfMoreThanOne!
// Total possible permutation for consonants = cCount!/ cCountOfMoreThanOne!
int cCountOfMoreThanOne = 1;
for(Map.Entry<Character, Integer> entry: cMap.entrySet()) {
if (entry.getValue() > 1) {
cCountOfMoreThanOne = (cCountOfMoreThanOne * factMap.get(entry.getValue())) % mod;
}
}
int cTotal = factMap.get(cCount) / cCountOfMoreThanOne;
// Permutation of all vowels = vCount!/(vCount - vCountToBeUsed)! => vCount!
// Duplicate of vowel vCountOfMoreThanOne!
// Total possible permutation for vowel = vCount!/ vCountOfMoreThanOne!
int vCountOfMoreThanOne = 1;
for(Map.Entry<Character, Integer> entry: vMap.entrySet()) {
if (entry.getValue() > 1) {
vCountOfMoreThanOne = (vCountOfMoreThanOne * factMap.get(entry.getValue())) % mod;
}
}
int vTotal = factMap.get(vCount) / vCountOfMoreThanOne;
// Multiply these two to get final permutation for both consonants and vowel permutation
return (cTotal * vTotal) % mod;
}
public static void main(String[] args) {
int res = new AnagramWithAlternateVowel_3().getCount("GADO");
System.out.println(res);
res = new AnagramWithAlternateVowel_3().getCount("AABCY");
System.out.println(res);
res = new AnagramWithAlternateVowel_3().getCount("XAABCY");
System.out.println(res);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment