What is the primary approach for Number of Strings Which Can Be Rearranged to Contain Substring?

State transition dynamic programming is the key pattern, tracking partial matches and extending them across string length n.

How do I handle repeated letters in this problem?

Use combinatorial formulas and factorials to account for multiple arrangements while updating DP states.

Why modulo 10^9 + 7 is used?

Because string counts grow exponentially with n, modulo arithmetic prevents integer overflow and keeps computations manageable.

Can this approach work for substrings longer than 4 letters?

Yes, the DP and combinatorial method generalizes to any fixed-length target substring, adjusting state tracking accordingly.

What is a common mistake when implementing the solution?

Ignoring the minimum required letters for "leet" or mismanaging state transitions can cause undercounting or overcounting valid strings.

#2930

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个整数 n 。如果一个字符串 s 只包含小写英文字母，且将 s 的字符重新排列后，新字符串包含子字符串 "leet" ，那么我们称字符串 s 是一个好字符串。比方说：字符串 "lteer" 是好字符串，因为重新排列后可以得到 "leetr" 。 "letl" 不是好字符串，因为…

数学动态规划组合数学

题目描述

给你一个整数 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⁵

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i, l, e, t)$ ，表示当前剩余字符串长度为 $i$ ，且已至少有 $l$ 个字符 'l', $e$ 个字符 'e' 和 $t$ 个字符 't'，构成的字符串是一个好字符串的方案数。那么答案为 $dfs(n, 0, 0, 0)$ 。

函数 $dfs(i, l, e, t)$ 的执行逻辑如下：

如果 $i = 0$ ，说明当前字符串已经构造完毕，如果 $l = 1$ , $e = 2$ 且 $t = 1$ ，说明当前字符串是一个好字符串，返回 $1$ ，否则返回 $0$ 。

否则，我们可以考虑在当前位置添加除 'l', 'e', 't' 以外的任意一个小写字母，一共有 $23$ 种，那么此时得到的方案数为 $dfs(i - 1, l, e, t) \times 23$ 。

我们也可以考虑在当前位置添加 'l'，此时得到的方案数为 $dfs(i - 1, \min(1, l + 1), e, t)$ 。同理，添加 'e' 和 't' 的方案数分别为 $dfs(i - 1, l, \min(2, e + 1), t)$ 和 $dfs(i - 1, l, e, \min(1, t + 1))$ 。累加起来，并对 $10^9 + 7$ 取模，即可得到 $dfs(i, l, e, t)$ 的值。

为了避免重复计算，我们可以使用记忆化搜索。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def stringCount(self, n: int) -> int:
        @cache
        def dfs(i: int, l: int, e: int, t: int) -> int:
            if i == 0:
                return int(l == 1 and e == 2 and t == 1)
            a = dfs(i - 1, l, e, t) * 23 % mod
            b = dfs(i - 1, min(1, l + 1), e, t)
            c = dfs(i - 1, l, min(2, e + 1), t)
            d = dfs(i - 1, l, e, min(1, t + 1))
            return (a + b + c + d) % mod

        mod = 10**9 + 7
        return dfs(n, 0, 0, 0)

speed

复杂度分析

指标	值
时间	complexity depends on n and the fixed length of substring "leet", generally O(n * length_of_pattern). Space complexity is O(n * length_of_pattern) for DP storage, which can be optimized using rolling arrays.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks about dynamic programming states and transitions for substrings.
question_mark
Checks understanding of combinatorial counting for rearrangements.
question_mark
Probes modulo arithmetic and overflow handling in large string counts.

warning

常见陷阱

外企场景

error
Forgetting that a good string must have at least one 'l', one 't', and two 'e'.
error
Double-counting arrangements when updating DP states.
error
Ignoring modulo operations, leading to incorrect results for large n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the target substring from "leet" to another fixed pattern.
arrow_right_alt
Count strings with exact character frequency constraints instead of minimum requirements.
arrow_right_alt
Compute the probability of randomly generated strings containing rearrangements of the pattern.

help

常见问题

外企场景

继续练习

#3154 到达第 K 级台阶的方案数 #3250 单调数组对的数目 I #3251 单调数组对的数目 II