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 <= 105In #2930 Number of Strings Which Can Be Rearranged to Contain Substring, the key insight is that the string only needs to contain enough characters so that some permutation includes the target substring. Instead of generating permutations, we count how many strings of length n have the required character frequencies.
The substring imposes minimum frequency constraints on certain characters. For example, if the substring requires multiple occurrences of a letter, the constructed string must contain at least those counts. A common strategy is to use combinatorics with inclusion–exclusion or a small dynamic programming state that tracks whether the required counts for each important character are satisfied.
We iterate through possible positions or build the string while tracking how many of the required characters have been used. Once all constraints are met, remaining positions can be filled with any of the alphabet characters. Precomputing powers or factorials helps compute combinations efficiently.
This avoids expensive permutation checks and reduces the problem to counting valid configurations. The resulting solution typically runs in O(n) time with constant or small auxiliary space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with character requirement states | O(n) | O(1) |
| Combinatorics with inclusion–exclusion counting | O(n) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
A good string must contain at least one <code>l</code>, one <code>t</code>, and two <code>e</code>.
Divide the problem into subproblems and use Dynamic Programming.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems involving combinatorics, counting strings, and inclusion–exclusion are common in FAANG-style interviews. While this exact problem may not appear, similar questions that combine math and dynamic programming frequently do.
The optimal approach counts strings that satisfy minimum character frequency constraints required by the substring. This can be solved using combinatorics with inclusion–exclusion or a small dynamic programming state that tracks required characters. The idea is to count valid strings directly instead of checking permutations.
Combinatorics helps count how many strings of length n satisfy certain character frequency requirements. By enforcing minimum counts for required letters and allowing any characters elsewhere, we can compute the number of valid configurations efficiently.
No complex data structure is required. Most solutions rely on counters for required characters along with mathematical utilities like fast exponentiation or precomputed combinations to calculate counts efficiently.