Medium

题目描述

给你一个整数 n 。

如果一个字符串 s 只包含小写英文字母，并且可以重新排列 s 的字符得到包含 "leet" 作为子字符串的新字符串，那么我们称字符串 s 是 好的 。

例如：

  • 字符串 "lteer" 是好的，因为我们可以重新排列得到 "leetr" 。
  • "letl" 不是好的，因为我们无法重新排列它来包含 "leet" 作为子字符串。

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

由于答案可能很大，请返回对 10^9 + 7 取余的结果。

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

示例 1：

输入：n = 4
输出：12
解释：可以重新排列得到包含 "leet" 作为子字符串的 12 个字符串是："eelt", "eetl", "elet", "elte", "etel", "etle", "leet", "lete", "ltee", "teel", "tele", 和 "tlee"。

示例 2：

输入：n = 10
输出：83943898
解释：长度为 10 且可以重新排列得到包含 "leet" 作为子字符串的字符串数目是 526083947580。因此答案是 526083947580 % (10^9 + 7) = 83943898。

提示：

  • 1 <= n <= 10^5
  • 好字符串必须包含至少一个 l、一个 t 和两个 e。
  • 将问题分解为子问题并使用动态规划。

解题思路

解题思路

这道题的关键是理解什么样的字符串可以重新排列得到包含 “leet” 的字符串。

要包含子字符串 “leet”，字符串必须至少包含：

  • 至少 1 个字母 ’l'
  • 至少 2 个字母 ’e'
  • 至少 1 个字母 ’t'

我们可以使用容斥原理来解决这个问题：

  1. 首先计算所有可能的字符串总数：26^n
  2. 然后减去不满足条件的字符串数量

设：

  • A = 缺少字母 ’l’ 的字符串集合
  • B = 缺少字母 ’e’（少于2个）的字符串集合
  • C = 缺少字母 ’t’ 的字符串集合

根据容斥原理： 好字符串数 = 总数 - |A∪B∪C| = 26^n - |A| - |B| - |C| + |A∩B| + |A∩C| + |B∩C| - |A∩B∩C|

其中：

  • |A| = 不包含 ’l’ 的字符串数 = 25^n
  • |C| = 不包含 ’t’ 的字符串数 = 25^n
  • |B| = 包含少于2个 ’e’ 的字符串数 = 25^n + n×25^(n-1)（0个e + 恰好1个e）
  • |A∩B|、|A∩C|、|B∩C|、|A∩B∩C| 类似计算

这种方法时间复杂度为 O(log n)，空间复杂度为 O(1)，是最优解法。

另一种思路是动态规划，但会更复杂一些，时间复杂度为 O(n)。

代码实现

class Solution {
public:
    int stringCount(int n) {
        const int MOD = 1e9 + 7;
        
        auto power = [&](long long base, int exp) {
            long long result = 1;
            base %= MOD;
            while (exp > 0) {
                if (exp & 1) result = (result * base) % MOD;
                base = (base * base) % MOD;
                exp >>= 1;
            }
            return result;
        };
        
        long long total = power(26, n);
        
        // 缺少 l 的字符串
        long long no_l = power(25, n);
        
        // 缺少 t 的字符串
        long long no_t = power(25, n);
        
        // e 少于 2 个的字符串：0个e + 1个e
        long long less_e = (power(25, n) + (1LL * n * power(25, n-1)) % MOD) % MOD;
        
        // 缺少 l 且 e 少于 2 个
        long long no_l_less_e = (power(24, n) + (1LL * n * power(24, n-1)) % MOD) % MOD;
        
        // 缺少 l 且缺少 t
        long long no_l_no_t = power(24, n);
        
        // 缺少 t 且 e 少于 2 个
        long long no_t_less_e = (power(24, n) + (1LL * n * power(24, n-1)) % MOD) % MOD;
        
        // 缺少 l、t 且 e 少于 2 个
        long long no_l_no_t_less_e = (power(23, n) + (1LL * n * power(23, n-1)) % MOD) % MOD;
        
        long long result = total - no_l - no_t - less_e + no_l_less_e + no_l_no_t + no_t_less_e - no_l_no_t_less_e;
        result = ((result % MOD) + MOD) % MOD;
        
        return result;
    }
};

class Solution:
    def stringCount(self, n: int) -> int:
        MOD = 10**9 + 7
        
        def power(base, exp):
            result = 1
            base %= MOD
            while exp > 0:
                if exp & 1:
                    result = (result * base) % MOD
                base = (base * base) % MOD
                exp >>= 1
            return result
        
        total = power(26, n)
        
        # 缺少 l 的字符串
        no_l = power(25, n)
        
        # 缺少 t 的字符串
        no_t = power(25, n)
        
        # e 少于 2 个的字符串：0个e + 1个e
        less_e = (power(25, n) + n * power(25, n-1)) % MOD
        
        # 缺少 l 且 e 少于 2 个
        no_l_less_e = (power(24, n) + n * power(24, n-1)) % MOD
        
        # 缺少 l 且缺少 t
        no_l_no_t = power(24, n)
        
        # 缺少 t 且 e 少于 2 个
        no_t_less_e = (power(24, n) + n * power(24, n-1)) % MOD
        
        # 缺少 l、t 且 e 少于 2 个
        no_l_no_t_less_e = (power(23, n) + n * power(23, n-1)) % MOD
        
        result = total - no_l - no_t - less_e + no_l_less_e + no_l_no_t + no_t_less_e - no_l_no_t_less_e
        return (result % MOD + MOD) % MOD

public class Solution {
    public int StringCount(int n) {
        const int MOD = 1000000007;
        
        long Power(long baseNum, int exp) {
            long result = 1;
            baseNum %= MOD;
            while (exp > 0) {
                if ((exp & 1) == 1) result = (result * baseNum) % MOD;
                baseNum = (baseNum * baseNum) % MOD;
                exp >>= 1;
            }
            return result;
        }
        
        long total = Power(26, n);
        
        // 缺少 l 的字符串
        long no_l = Power(25, n);
        
        // 缺少 t 的字符串
        long no_t = Power(25, n);
        
        // e 少于 2 个的字符串：0个e + 1个e
        long less_e = (Power(25, n) + ((long)n * Power(25, n-1)) % MOD) % MOD;
        
        // 缺少 l 且 e 少于 2 个
        long no_l_less_e = (Power(24, n) + ((long)n * Power(24, n-1)) % MOD) % MOD;
        
        // 缺少 l 且缺少 t
        long no_l_no_t = Power(24, n);
        
        // 缺少 t 且 e 少于 2 个
        long no_t_less_e = (Power(24, n) + ((long)n * Power(24, n-1)) % MOD) % MOD;
        
        // 缺少 l、t 且 e 少于 2 个
        long no_l_no_t_less_e = (Power(23, n) + ((long)n * Power(23, n-1)) % MOD) % MOD;
        
        long result = total - no_l - no_t - less_e + no_l_less_e + no_l_no_t + no_t_less_e - no_l_no_t_less_e;
        return (int)((result % MOD + MOD) % MOD);
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var stringCount = function(n) {
    const MOD = 1e9 + 7;
    
    function power(base, exp) {
        let result = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp & 1) result = (result * base) % MOD;
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return result;
    }
    
    const total = power(26, n);
    
    // 缺少 l 的字符串
    const no_l = power(25, n);
    
    // 缺少 t 的字符串
    const no_t = power(25, n);
    
    // e 少于 2 个的字符串：0个e + 1个e
    const less_e = (power(25, n) + (n * power(25, n-1)) % MOD) % MOD;
    
    // 缺少 l 且 e 少于 2 个
    const no_l_less_e = (power(24, n) + (n * power(24, n-1)) % MOD) % MOD;
    
    // 缺少 l 且缺少 t
    const no_l_no_t = power(24, n);
    
    // 缺少 t 且 e 少于 2 个
    const no_t_less_e = (power(24, n) + (n * power(24, n-1)) % MOD) % MOD;
    
    // 缺少 l、t 且 e 少于 2 个
    const no_l_no_t_less_e = (power(23, n) + (n * power(23, n-1)) % MOD) % MOD;
    
    let result = total - no_l - no_t - less_e + no_l_less_e + no_l_no_t + no_t_less_e - no_l_no_t_less_e;
    return ((result % MOD) + MOD) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大O表示法
时间复杂度O(log n)
空间复杂度O(1)

相关题目