Problem
You are given a string s containing one or more words. Every consecutive pair of words is separated by a single space ' '.
A string t is an anagram of string s if the ith word of t is a permutation of the ith word of s.
- For example,
"acb dfe"is an anagram of"abc def", but"def cab"and"adc bef"are not.
Return **the number of *distinct anagrams* of **s. Since the answer may be very large, return it *modulo* 109 + 7.
Example 1:
Input: s = "too hot"
Output: 18
Explanation: Some of the anagrams of the given string are "too hot", "oot hot", "oto toh", "too toh", and "too oht".
Example 2:
Input: s = "aa"
Output: 1
Explanation: There is only one anagram possible for the given string.
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters and spaces' '.There is single space between consecutive words.
Solution (Java)
class Solution {
public int countAnagrams(String str) {
Map<Integer,Long> map = new HashMap<>();
int mod = 1000000000 + 7;
long pro = 1;
long ans = 1;
for(int i = 1 ; i <= 100000 ; i++) {
pro = (pro * i) % mod;
map.put(i, pro);
}
for(String s : str.split(" ")) {
long num = map.get(s.length());
long den = 1;
int[] freq = new int[26];
for(char ch : s.toCharArray()) freq[ch - 'a']++;
for(int ele : freq) {
if(ele != 0)
den = (den * map.get(ele)) % mod;
}
long curr = (num * pow(den, mod - 2)) % mod;
ans = (ans * curr) % mod;
}
return (int)ans;
}
long pow(long a,long n) {
int mod = 1000000000 + 7;
long res = 1;
while(n > 0) {
if(n % 2 == 1) {
res = (res * a) % mod;
n--;
}
else {
a = (a * a) % mod;
n = n / 2;
}
}
return res;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).