Last active
May 2, 2022 14:06
-
-
Save nayyaung/d9445d4fa3b6914bd642e583e23a391a to your computer and use it in GitHub Desktop.
Count anagram that starts with consonant and has no consecutive vowels
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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