2514. Count Anagrams LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2514. Count Anagrams LeetCode Solution with the best time and space complexity. The solution to Count Anagrams problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Anagrams solution in C++
Count Anagrams solution in Java
Count Anagrams solution in Python
Additional Resources

2514. Count Anagrams LeetCode Solution image

Problem Statement of Count Anagrams

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2514. Count Anagrams LeetCode Solution in C++

class Solution {
 public:
  int countAnagrams(string s) {
    const int n = s.length();
    const auto [fact, invFact] = getFactAndInvFact(n);
    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:
  static constexpr int kMod = 1'000'000'007;

  pair<vector<long>, vector<long>> getFactAndInvFact(int n) {
    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};
  }
};
/* code provided by PROGIEZ */

2514. Count Anagrams LeetCode Solution in Java

class Solution {
  public int countAnagrams(String s) {
    final int n = s.length();
    final long[][] factAndInvFact = getFactAndInvFact(n);
    final long[] fact = factAndInvFact[0];
    final long[] invFact = factAndInvFact[1];
    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 static final int kMod = 1_000_000_007;

  private long[][] getFactAndInvFact(int n) {
    long[] fact = new long[n + 1];
    long[] invFact = new long[n + 1];
    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;
    }
    return new long[][] {fact, invFact};
  }
}
// code provided by PROGIEZ

2514. Count Anagrams LeetCode Solution in Python

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
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents