统计同位异构字符串数目

题目

2514. 统计同位异构字符串数目

---

给你一个字符串 s ，它包含一个或者多个单词。单词之间用单个空格 ' ' 隔开。

如果字符串 t 中第 i 个单词是 s 中第 i 个单词的一个 排列 ，那么我们称字符串 t 是字符串 s 的同位异构字符串。

• 比方说，"acb dfe" 是 "abc def" 的同位异构字符串，但是 "def cab" 和 "adc bef" 不是。

请你返回 s 的同位异构字符串的数目，由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。

示例 1：

输入：s = "too hot"
输出：18
解释：输入字符串的一些同位异构字符串为 "too hot" ，"oot hot" ，"oto toh" ，"too toh" 以及 "too oht" 。

示例 2：

输入：s = "aa"
输出：1
解释：输入字符串只有一个同位异构字符串。

提示：

• 1 <= s.length <= 10^5
• s 只包含小写英文字母和空格 ' ' 。
• 相邻单词之间由单个空格隔开。

题解

方法一：

思路

求出每个单词的多重全排列，然后根据乘法原理，累乘即可。

设第i个单词的字母a出现的次数为$a_i$

答案是$\prod \frac{(a_i+b_i+\cdots+z_i)!}{a_i!b_i!\cdots z_i!}$

我们可以预处理阶乘的逆元减小时间复杂度。

代码

class Solution {
public:
    using ll = long long;
    const ll MOD = 1e9+7;
    ll fpow(ll x, ll p) {
        ll rt = 1;
        while (p) {
            if (p&1) rt *= x, rt%=MOD;
            x = x*x; x%=MOD;
            p>>=1;
        }
        return rt;
    }
    int countAnagrams(string s) {
        s.push_back(' ');
        int n = s.size();
        ll fac[n], inv[n];
        fac[0] = 1;
        for (int i=1; i<n; i++) {
            fac[i] = fac[i-1]*i%MOD;
        }
        inv[n-1] = fpow(fac[n-1], MOD-2);
        for (int i=n-2; i>=0; i--) {
            inv[i] = inv[i+1]*(i+1)%MOD;
        }
        ll ans = 1;
        int c[26] = {0};
        for (int i=0; i<n; i++) {
            if (s[i] == ' ') {
                ans *= fac[accumulate(c, c+26, 0)];
                ans %= MOD;
                for (int j=0; j<26; j++) {
                    ans *= inv[c[j]];
                    ans %= MOD;
                }
                memset(c, 0, sizeof(c));
            } else c[s[i]-'a']++;
        }
        return ans;        
    }
};