Easy to Understand Java Solution Permutations and Inverse Factorial
Intuition\n Describe your first thoughts on how to solve this problem. \nThe idea is how to calcuate number of permutations with duplicates.\n\n# Approach\n Des
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe idea is how to calcuate number of permutations with duplicates.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor string such as "AAABBCCD", the length of string is 8, and has 3 \'A\'s, 2 \'B\'s, 2 \'C\'s, and 1 \'D\'.\n\nPermutations of duplicates only contribute to one of unique permutation, therefore, number of permuations of the entire string needs to be divided by number of permuations of each duplicate.\n\nThus, the the number of permutations of string "AAABBCCD" is 8!/(3!*2!*2!*1!).\n\nThe next question is how to calcuate inverse of factorials when number is large.\n\nLet A * A\' = 1 and MOD = 1000000007, then (A * A\') = 1 (mod MOD), we need to calculate (A * A\') = 1 (mod MOD). Then \n\n```\n(A ^ (MOD - 2) * A) % MOD = A ^ (MOD - 1) % MOD = 1 % MOD\n```\n\nWe used [Fermat\'s little theorem](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem), let P be a prime number, then\n\n```\nA ^ P = A (mod P)\n```\n\nThus, if we want to calculate A\', we just calculate\n\n```\nA ^ (MOD - 2)\n\n```\nBecause MOD = 1000000007 and 1000000007 is a prime number.\n\n# Complexity\nLet maximum length of individual string is m and number of strings be n, then time complexity is O(m) for calculating factorial, O(n * log(MOD)) for calculating inverse factorial ~ O(n).\nIf there are n individual strings, the time to calculate number of permutations is O(m * constant).\n\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(m + n).\n\nWe need to store information of factorial and inverse factorial array, space complexity of this part is O(m). Because the auxiliary array of `String[] strs`, space complexity of this part is O(m * n).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m * n).\n\n# Code\n```\nclass Solution {\n    private static final int MOD = 1000000007;\n    public int countAnagrams(String s) {\n        String[] strs = s.split(" ");\n        long result = 1;\n        int maxLen = 0;\n        for (String str : strs) {            \n            maxLen = Math.max(maxLen, str.length());\n        }\n        int[] factorial = getFactorial(maxLen);\n        int[] invFactorial = getInverseFactorial(maxLen, factorial);\n        int[] count = new int[26];\n        int len = 0;\n        long numOfPermutations = 0;\n        for (String str : strs) {\n            Arrays.fill(count, 0);\n            len = str.length();\n            for (int i = 0; i < len; i++) {\n                count[str.charAt(i) - \'a\']++;\n            }\n            numOfPermutations = factorial[len];\n            for (int i = 0; i < 26; i++) {\n                if (count[i] > 0) {\n                    numOfPermutations = (numOfPermutations * invFactorial[count[i]]) % MOD;\n                }\n            }\n            result = (result * numOfPermutations) % MOD;\n        }\n        return (int) result;\n    }\n    private int[] getFactorial(int num) {\n        int[] factorial = new int[num + 1];\n        factorial[0] = 1;\n        for (int i = 1; i <= num; i++) {\n            factorial[i] = (int) ((1L * factorial[i - 1] * i) % MOD);\n        }\n        return factorial;\n    }\n    private int[] getInverseFactorial(int num, int[] factorial) {\n        int[] invFactorial = new int[num + 1];\n        for (int i = 1; i <= num; i++) {\n            invFactorial[i] = (int) powMod(factorial[i], MOD - 2) % MOD;\n        }\n        return invFactorial;\n    }\n    private long powMod(long num, int pow) {\n        long result = 1;\n        while (pow >= 1) {\n            if (pow % 2 == 1) {\n                result = (result * num) % MOD;\n            }\n            pow /= 2;\n            num = (num * num) % MOD;\n        }\n        return result;\n    }\n}\n\n```
['Combinatorics', 'Java']