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:
"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 <= 105Problem Overview: You are given an integer n and must count how many lowercase strings of length n can be rearranged so that the substring "leet" appears. Because rearrangement is allowed, the task becomes a counting problem: the string must contain at least one l, two e's, and one t. Any valid multiset of characters that satisfies these minimum counts can always be rearranged so that "leet" appears as a contiguous substring.
Approach 1: Counting Permutations and Repetitions (Combinatorics) (Time: O(1), Space: O(1))
This approach treats the problem purely as a combinatorics counting task. A valid string must contain at least the characters required to build "leet": one l, two e's, and one t. The remaining n - 4 positions can contain any lowercase letter. The challenge is counting all strings that satisfy these minimum requirements without double counting. The typical technique uses inclusion–exclusion: start from the total number of strings 26^n, then subtract cases where constraints are violated (missing l, missing t, or fewer than two e's). Handling the e condition requires counting both zero and one occurrence cases. Modular arithmetic keeps values within limits. This method relies heavily on combinatorics and math insights and works in constant time once formulas are derived.
Approach 2: Dynamic Programming with String Constraints (Time: O(n), Space: O(1))
The dynamic programming solution builds the string character by character while tracking how many required characters have been collected so far. Define a DP state representing counts of the required letters: whether l has appeared, how many e's have appeared (0, 1, or at least 2), and whether t has appeared. At each step, iterate through the 26 possible characters and update the state transitions. Characters that are not l, e, or t simply keep the constraint state unchanged. The DP accumulates the number of valid strings for each prefix length, and the final answer is the state where all constraints are satisfied. Because the number of states is small and fixed, the algorithm runs in linear time with constant memory. This formulation is a classic constraint-counting DP related to dynamic programming.
Recommended for interviews: The combinatorics approach is typically the expected optimal answer because it reduces the problem to counting with inclusion–exclusion and runs in constant time. However, explaining the DP approach first can demonstrate strong reasoning about constraints and state transitions. Showing both methods signals a solid understanding of counting problems and algorithmic modeling.
This approach calculates the total number of permutations for strings of length n that can include the substring 'leet' by computing and combining permutations and factorial properties for character placement.
This code leverages modular arithmetic and combinatorial principles to calculate the number of valid permutations. It uses Fermat's Little Theorem to get the modular multiplicative inverse and efficiently handles operations via repeated squaring for quick power computations.
Time Complexity: O(n) due to factorial calculations.
Space Complexity: O(1), as no extra space proportional to input size is used.
In dynamic programming, substring constraints are managed systematically, solving smaller subproblems consistently while capturing 'leet' occurrence opportunities.
This dynamic programming solution defines states and transitions to track the contribution of each character towards including 'leet' in the string. Each state captures whether 'l', 'e', 'e', 't' are part of any prefix.
Python
Time Complexity: O(n * 16), modified by constant. Space Complexity: O(n * 16), due to DP table storage.
We design a function dfs(i, l, e, t), which represents the number of good strings that can be formed when the remaining string length is i, and there are at least l characters 'l', e characters 'e' and t characters 't'. The answer is dfs(n, 0, 0, 0).
The execution logic of the function dfs(i, l, e, t) is as follows:
If i = 0, it means that the current string has been constructed. If l = 1, e = 2 and t = 1, it means that the current string is a good string, return 1, otherwise return 0.
Otherwise, we can consider adding any lowercase letter other than 'l', 'e', 't' at the current position, there are 23 in total, so the number of schemes obtained at this time is dfs(i - 1, l, e, t) times 23.
We can also consider adding 'l' at the current position, and the number of schemes obtained at this time is dfs(i - 1, min(1, l + 1), e, t). Similarly, the number of schemes for adding 'e' and 't' are dfs(i - 1, l, min(2, e + 1), t) and dfs(i - 1, l, e, min(1, t + 1)) respectively. Add them up and take the modulus of 10^9 + 7 to get the value of dfs(i, l, e, t).
To avoid repeated calculations, we can use memorization search.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string.
Python
Java
C++
Go
TypeScript
We can consider reverse thinking, that is, calculate the number of strings that do not contain the substring "leet", and then subtract this number from the total.
We divide it into the following cases:
a: represents the number of schemes where the string does not contain the character 'l', so we have a = 25^n.b: similar to a, represents the number of schemes where the string does not contain the character 't', so we have b = 25^n.c: represents the number of schemes where the string does not contain the character 'e' or only contains one character 'e', so we have c = 25^n + n times 25^{n - 1}.ab: represents the number of schemes where the string does not contain the characters 'l' and 't', so we have ab = 24^n.ac: represents the number of schemes where the string does not contain the characters 'l' and 'e' or only contains one character 'e', so we have ac = 24^n + n times 24^{n - 1}.bc: similar to ac, represents the number of schemes where the string does not contain the characters 't' and 'e' or only contains one character 'e', so we have bc = 24^n + n times 24^{n - 1}.abc: represents the number of schemes where the string does not contain the characters 'l', 't' and 'e' or only contains one character 'e', so we have abc = 23^n + n times 23^{n - 1}.Then according to the inclusion-exclusion principle, a + b + c - ab - ac - bc + abc is the number of strings that do not contain the substring "leet".
The total number tot = 26^n, so the answer is tot - (a + b + c - ab - ac - bc + abc), remember to take the modulus of 10^9 + 7.
The time complexity is O(log n), and the space complexity is O(1). Here, n is the length of the string.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Counting Permutations and Repetitions | Time Complexity: O(n) due to factorial calculations. |
| Dynamic Programming with String Constraints | Time Complexity: O(n * 16), modified by constant. Space Complexity: O(n * 16), due to DP table storage. |
| Memorization Search | — |
| Reverse Thinking + Inclusion-Exclusion Principle | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Permutations and Repetitions (Combinatorics) | O(1) | O(1) | Best for deriving a mathematical formula using inclusion-exclusion when constraints involve required character counts. |
| Dynamic Programming with String Constraints | O(n) | O(1) | Useful when modeling the problem as state transitions for required characters or when the combinatorics formula is hard to derive. |
2930. Number of Strings Which Can Be Rearranged to Contain Substring | DP | BiWeekly 117 • Tech Courses • 828 views views
Watch 6 more video solutions →Practice Number of Strings Which Can Be Rearranged to Contain Substring with our built-in code editor and test cases.
Practice on FleetCode