重新排列后包含指定子字符串的字符串数目

标签: 数学动态规划组合数学

难度: Medium

给你一个整数 n 。

如果一个字符串 s 只包含小写英文字母，且将 s 的字符重新排列后，新字符串包含 子字符串 "leet" ，那么我们称字符串 s 是一个好字符串。

比方说：

字符串 "lteer" 是好字符串，因为重新排列后可以得到 "leetr" 。
"letl" 不是好字符串，因为无法重新排列并得到子字符串 "leet" 。

请你返回长度为 n 的好字符串总数目。

由于答案可能很大，将答案对 10⁹ + 7 取余后返回。

子字符串 是一个字符串中一段连续的字符序列。

示例 1：

输入：n = 4
输出：12
解释：总共有 12 个字符串重新排列后包含子字符串 "leet" ："eelt" ，"eetl" ，"elet" ，"elte" ，"etel" ，"etle" ，"leet" ，"lete" ，"ltee" ，"teel" ，"tele" 和 "tlee" 。

示例 2：

输入：n = 10
输出：83943898
解释：长度为 10 的字符串重新排列后包含子字符串 "leet" 的方案数为 526083947580 。所以答案为 526083947580 % (10⁹ + 7) = 83943898 。

提示：

1 <= n <= 10⁵

Submission

运行时间: 27 ms

内存: 16.0 MB

class Solution:
    def stringCount(self, n: int) -> int:
        mod = 10**9+7
        
        if n <= 3:
            return 0 
        
        
        # 没有L
        a = pow(25, n, mod)
        # 没有t
        b = pow(25, n, mod)
        # 只有一个e，没有e
        c = n*pow(25,n-1, mod) + pow(25, n, mod)
        
        # 没有L，没有t
        ab = pow(24, n, mod)
        
        # 没有l, 只有一个e， 没有e
        ac = n*pow(24, n-1, mod) + pow(24, n, mod)
        
        bc = n*pow(24, n-1, mod) + pow(24, n, mod)
        
        abc = n*pow(23, n-1, mod) + pow(23, n, mod)
        
        return (pow(26, n, mod) - a - b - c +ab+ac+bc - abc) % mod

Explain

此题解采用的是容斥原理来计算字符串数目。主要思路是计算出所有可能的长度为 n 的字符串数目，然后依次减去不包含 'l', 'e', 或 't' 的字符串数目，并对多次减去的部分使用容斥原理进行调整。首先计算出所有可能的字符串数目，即包含所有小写英文字母的字符串数目为 26^n。随后，分别计算出不包含 'l', 'e', 或 't' 的字符串数目，这些情况下的字符串数目分别为 25^n。对于同时不包含两个或三个特定字符的情况，根据容斥原理，需要进行加减调整，比如同时不包含 'l' 和 't' 的字符串数目为 24^n 等。最终通过加减这些数目，使用模运算确保结果在合理范围内，得到包含子字符串 'leet' 的字符串总数。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def stringCount(self, n: int) -> int:
        mod = 10**9+7
        
        if n <= 3:
            return 0 # 如果 n <= 3，不可能形成包含 'leet' 的字符串
        
        # 计算不包含某个字符的字符串数目
        a = pow(25, n, mod) # 不包含 'l'
        b = pow(25, n, mod) # 不包含 't'
        c = n*pow(25, n-1, mod) + pow(25, n, mod) # 只有一个或没有 'e'
        
        # 计算不包含两个字符的字符串数目
        ab = pow(24, n, mod) # 不包含 'l' 和 't'
        ac = n*pow(24, n-1, mod) + pow(24, n, mod) # 不包含 'l'，只有一个或没有 'e'
        bc = n*pow(24, n-1, mod) + pow(24, n, mod) # 不包含 't'，只有一个或没有 'e'
        
        # 计算不包含三个字符的字符串数目
        abc = n*pow(23, n-1, mod) + pow(23, n, mod) # 不包含 'l', 't', 只有一个或没有 'e'
        
        # 使用容斥原理计算最终答案
        return (pow(26, n, mod) - a - b - c + ab + ac + bc - abc) % mod

Explore

在计算不包含字符'e'的字符串数目时，需要考虑字符串中'e'字符出现次数的不同情况，因为'e'可以出现0次或1次。公式中的pow(25, n, mod)计算的是'e'一次也不出现的情况，而n*pow(25, n-1, mod)计算的是'e'恰好出现一次的情况（e可以出现在n个位置中的任何一个，剩余位置可以是除e之外的25个字母）。相比之下，'l'和't'在题解中被认为完全不出现，因此只使用了pow(25, n, mod)来计算。

这个公式用于计算同时不包含两个特定字符（例如'l'和'e'）的字符串数目。pow(24, n, mod)计算的是两个字符都不出现的情况。而n*pow(24, n-1, mod)计算的是其中一个字符恰好出现一次的情况，另一个字符不出现。这里的n表示该特定字符可以出现在字符串的任何一个位置，而其他位置由剩下的24个字符填充。因此，这个公式确保了在所有可能的位置上恰好出现一个特定字符的所有情况都被正确计算。

容斥原理用于计算涉及多个集合的总元素数。在首次减去不包含某些字符的字符串数目时（例如单独的'l', 'e', 't'），会出现对于同时不包含两个字符（例如'l'和't'）的字符串的多次减除。因此，需要加回这部分数目。然而，当加回不包含两个字符的情况时，包含三个字符都不出现的情况又被多次添加，因此需要再次减去不包含三个字符的情况，以确保每种情况被正确计数。

10^9+7是一个大质数，常用于编程中以避免整数溢出，并保持结果在一个可管理的范围内。在进行模运算时，所有的数学操作（如加法、乘法）都是在这个模下完成的，这意味着结果永远不会超过10^9+7，从而避免了大数的直接存储和操作可能引起的溢出问题。使用这种方法可以确保即使对于非常大的n，计算结果仍然是正确和可控的。