Description
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 <= 105
s
consists of lowercase English letters and spaces ' '
.
- There is single space between consecutive words.
Solutions
Solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | mod = 10**9 + 7
f = [1]
for i in range(1, 10**5 + 1):
f.append(f[-1] * i % mod)
class Solution:
def countAnagrams(self, s: str) -> int:
ans = 1
for w in s.split():
cnt = Counter(w)
ans *= f[len(w)]
ans %= mod
for v in cnt.values():
ans *= pow(f[v], -1, mod)
ans %= mod
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | import java.math.BigInteger;
class Solution {
private static final int MOD = (int) 1e9 + 7;
public int countAnagrams(String s) {
int n = s.length();
long[] f = new long[n + 1];
f[0] = 1;
for (int i = 1; i <= n; ++i) {
f[i] = f[i - 1] * i % MOD;
}
long p = 1;
for (String w : s.split(" ")) {
int[] cnt = new int[26];
for (int i = 0; i < w.length(); ++i) {
++cnt[w.charAt(i) - 'a'];
}
p = p * f[w.length()] % MOD;
for (int v : cnt) {
p = p * BigInteger.valueOf(f[v]).modInverse(BigInteger.valueOf(MOD)).intValue()
% MOD;
}
}
return (int) p;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | class Solution {
public:
const int mod = 1e9 + 7;
int countAnagrams(string s) {
stringstream ss(s);
string w;
long ans = 1, mul = 1;
while (ss >> w) {
int cnt[26] = {0};
for (int i = 1; i <= w.size(); ++i) {
int c = w[i - 1] - 'a';
++cnt[c];
ans = ans * i % mod;
mul = mul * cnt[c] % mod;
}
}
return ans * pow(mul, mod - 2) % mod;
}
long pow(long x, int n) {
long res = 1L;
for (; n; n /= 2) {
if (n % 2) res = res * x % mod;
x = x * x % mod;
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | const mod int = 1e9 + 7
func countAnagrams(s string) int {
ans, mul := 1, 1
for _, w := range strings.Split(s, " ") {
cnt := [26]int{}
for i, c := range w {
i++
cnt[c-'a']++
ans = ans * i % mod
mul = mul * cnt[c-'a'] % mod
}
}
return ans * pow(mul, mod-2) % mod
}
func pow(x, n int) int {
res := 1
for ; n > 0; n >>= 1 {
if n&1 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}
|
Solution 2