Skip to content

2514. Count Anagrams 👍

  • Time: $O(|\texttt{s}|)$
  • Space: $O(|\texttt{s}|)$
 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
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int countAnagrams(string s) {
    constexpr int kMod = 1'000'000'007;
    const int n = s.length();
    const auto [fact, invFact] = getFactAndInvFact(n, kMod);
    int ans = 1;
    istringstream iss(s);

    for (string word; iss >> word;) {
      ans = ans * fact[word.length()] % kMod;
      vector<int> count(26);
      for (const char c : word)
        ++count[c - 'a'];
      for (const int freq : count)
        ans = ans * invFact[freq] % kMod;
    }

    return ans;
  }

 private:
  pair<vector<long>, vector<long>> getFactAndInvFact(int n, int kMod) {
    vector<long> fact(n + 1);
    vector<long> invFact(n + 1);
    vector<long> inv(n + 1);
    fact[0] = invFact[0] = 1;
    inv[0] = inv[1] = 1;

    for (int i = 1; i <= n; ++i) {
      if (i >= 2)
        inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
      fact[i] = fact[i - 1] * i % kMod;
      invFact[i] = invFact[i - 1] * inv[i] % kMod;
    }

    return {fact, invFact};
  }
};

 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
30
31
32
33
34
35
class Solution {
  public int countAnagrams(String s) {
    final int kMod = 1_000_000_007;
    final int n = s.length();
    long[] fact = new long[n + 1];
    long[] invFact = new long[n + 1];
    getFactAndInvFact(n, kMod, fact, invFact);

    long ans = 1;

    for (final String word : s.split(" ")) {
      ans = ans * fact[word.length()] % kMod;
      int[] count = new int[26];
      for (final char c : word.toCharArray())
        ++count[c - 'a'];
      for (final int freq : count)
        ans = ans * invFact[freq] % kMod;
    }

    return (int) ans;
  }

  private void getFactAndInvFact(int n, int kMod, long[] fact, long[] invFact) {
    long[] inv = new long[n + 1];
    fact[0] = invFact[0] = 1;
    inv[0] = inv[1] = 1;

    for (int i = 1; i <= n; ++i) {
      if (i >= 2)
        inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
      fact[i] = fact[i - 1] * i % kMod;
      invFact[i] = invFact[i - 1] * inv[i] % kMod;
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def countAnagrams(self, s: str) -> int:
    ans = 1

    for word in s.split():
      ans = ans * math.factorial(len(word))
      count = collections.Counter(word)
      for freq in count.values():
        ans //= math.factorial(freq)

    return ans % 1_000_000_007