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

You are given an integer n.

A string s is called good if it contains only lowercase English characters and it is possible to rearrange the characters of s such that the new string contains "leet" as a substring.

For example:

• The string "lteer" is good because we can rearrange it to form "leetr" .
• "letl" is not good because we cannot rearrange it to contain "leet" as a substring.

Return the total number of good strings of length n.

Since the answer may be large, return it modulo 109 + 7.

A substring is a contiguous sequence of characters within a string.

 

Example 1:

Input: n = 4
Output: 12
Explanation: The 12 strings which can be rearranged to have "leet" as a substring are: "eelt", "eetl", "elet", "elte", "etel", "etle", "leet", "lete", "ltee", "teel", "tele", and "tlee".

Example 2:

Input: n = 10
Output: 83943898
Explanation: The number of strings with length 10 which can be rearranged to have "leet" as a substring is 526083947580. Hence the answer is 526083947580 % (109 + 7) = 83943898.

 

Constraints:

• 1 <= n <= 105

/* 
题目思路：
使用 Java Stream 来简化计算过程。我们依然使用组合数学计算选择位置的方式，并且使用快速幂计算排列的方式。最后结果对 10^9 + 7 取余。
*/

import java.math.BigInteger;
import java.util.stream.LongStream;

public class GoodStringStream {
    private static final int MOD = 1000000007;

    public static void main(String[] args) {
        int n = 10;  // 示例输入
        System.out.println(countGoodStrings(n));
    }

    public static long countGoodStrings(int n) {
        if (n < 4) return 0;
        long totalWays = factorial(n);
        long invalidWays = factorial(n - 4);
        long permutationsOfLeet = factorial(4);
        long result = (totalWays * modInverse(invalidWays * permutationsOfLeet % MOD, MOD)) % MOD;
        return result;
    }

    private static long factorial(int n) {
        return LongStream.rangeClosed(1, n)
                .reduce(1, (long a, long b) -> a * b % MOD);
    }

    private static long modInverse(long a, int mod) {
        return BigInteger.valueOf(a).modInverse(BigInteger.valueOf(mod)).longValue();
    }
}

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

O(log n)

O(1)