Count Anagrams Solution in Java

Problem Description

Ah, the classic “Count Anagrams” problem! It’s like trying to find out how many ways you can rearrange your sock drawer without losing your sanity. Imagine you have a bunch of words, and you want to know how many unique ways you can rearrange the letters in those words. Sounds simple, right? Well, it’s not just about shuffling letters like a deck of cards; you have to account for duplicates!

For instance, if you have the word “aabb”, you can rearrange it to form “abab”, “baba”, and “aabb”, but you can’t count “aabb” twice because that would be cheating! So, the task is to count all the unique anagrams of each word in a given string, and then return the total count modulo 10^9 + 7.

Code Solution


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};
  }
}

Approach Explanation

The code uses combinatorial mathematics to count the anagrams efficiently. It calculates the factorial of the length of each word and divides it by the factorial of the frequency of each character in that word. This way, it avoids counting duplicates. The results are computed modulo 10^9 + 7 to prevent overflow and keep the numbers manageable.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n + k)
Space Complexity	O(n)

Real-World Example

Imagine you’re at a party, and you have a bag of colored marbles. You want to know how many unique ways you can arrange them on a table. If you have 2 red marbles and 2 blue marbles, you can arrange them in several ways, but you can’t count the same arrangement twice. This is exactly what the Count Anagrams problem is about—finding unique arrangements of letters (or marbles) while considering duplicates.