Skip to main content
Talentd

Number of Strings Which Can Be Rearranged to Contain Substring - Solution & Explanation

MediumMathDynamic ProgrammingCombinatorics31 min readAsked at: Meesho
Practice this problem

Problem Statement

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

Approach Overview

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

Approach 1: Counting Permutations and Repetitions

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) due to factorial calculations.
Space Complexity: O(1), as no extra space proportional to input size is used.

Try this approach in the editor →

Approach 2: Dynamic Programming with String Constraints

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.

Code

Python

Python

Complexity

Time Complexity: O(n * 16), modified by constant. Space Complexity: O(n * 16), due to DP table storage.

Try this approach in the editor →

Approach 3: Memorization Search

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Reverse Thinking + Inclusion-Exclusion Principle

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:

  • Case a: represents the number of schemes where the string does not contain the character 'l', so we have a = 25^n.
  • Case b: similar to a, represents the number of schemes where the string does not contain the character 't', so we have b = 25^n.
  • Case 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}.
  • Case ab: represents the number of schemes where the string does not contain the characters 'l' and 't', so we have ab = 24^n.
  • Case 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}.
  • Case 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}.
  • Case 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Counting Permutations and Repetitions

Time Complexity: O(n) due to factorial calculations.
Space Complexity: O(1), as no extra space proportional to input size is used.

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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 ConstraintsO(n)O(1)Useful when modeling the problem as state transitions for required characters or when the combinatorics formula is hard to derive.

Video Solution

2930. Number of Strings Which Can Be Rearranged to Contain Substring | DP | BiWeekly 117 • Tech Courses • 852 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Number of Strings Which Can Be Rearranged to Contain Substring easy or hard?
This problem is generally rated Medium because the brute counting idea is straightforward but deriving the correct combinatorics formula requires careful handling of constraints like two occurrences of 'e'. Dynamic programming offers a more intuitive but slightly slower alternative.
Number of Strings Which Can Be Rearranged to Contain Substring Python/Java solution
Python, Java, C++, and JavaScript implementations typically compute powers of 26 with modular arithmetic and apply inclusion–exclusion formulas. The DP version uses a small state array updated for each position in the string and works well in Python or Java.
How to solve Number of Strings Which Can Be Rearranged to Contain Substring in O(1)?
Treat the problem as counting valid character multisets. A valid string must contain at least one 'l', two 'e's, and one 't'. Compute the total number of strings (26^n) and subtract invalid cases such as missing 'l', missing 't', or having fewer than two 'e's using inclusion–exclusion. The formula evaluation takes constant time.
What is the best approach for Number of Strings Which Can Be Rearranged to Contain Substring?
The optimal approach uses combinatorics with inclusion–exclusion. Instead of generating strings, count all possible strings (26^n) and subtract cases that violate the required characters for "leet". The final formula runs in O(1) time and O(1) space using modular arithmetic.
Is Number of Strings Which Can Be Rearranged to Contain Substring asked at Google/Amazon/Meta?
Problems combining combinatorics and counting constraints are common in interviews at companies like Google, Amazon, and Meta. Variations of this question appear when evaluating a candidate’s ability to apply inclusion–exclusion, dynamic programming states, and modular arithmetic.
What data structure is used in Number of Strings Which Can Be Rearranged to Contain Substring?
The combinatorics solution does not require special data structures and relies mainly on arithmetic and exponentiation. The dynamic programming solution uses a small DP state table tracking whether 'l' and 't' appear and how many 'e's have been seen so far.
What is the time complexity of Number of Strings Which Can Be Rearranged to Contain Substring?
The combinatorics solution runs in O(1) time because it evaluates a constant number of power and arithmetic operations. A dynamic programming alternative processes the string length sequentially and runs in O(n) time with O(1) space due to a small fixed number of states.

Ready to solve this problem?

Practice Number of Strings Which Can Be Rearranged to Contain Substring with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Vowels Permutation