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.
| 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. |
| 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