#2930

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Strings Which Can Be Rearranged to Contain Substring

Calculate how many strings of length n can be rearranged to contain "leet" using dynamic programming and combinatorics.

Problem Statement

Given an integer n, determine the number of strings of length n consisting of lowercase English letters that can be rearranged such that the string contains "leet" as a substring. Each string is considered good if at least one 'l', one 't', and two 'e' are present, enabling a rearrangement forming "leet".

Return the count of such good strings modulo 10^9 + 7. For example, with n = 4, strings like "eelt", "leet", and "tlee" are valid because they can be rearranged to contain "leet". Constraints: 1 <= n <= 10^5.

Examples

Example 1

Input: n = 4

Output: 12

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

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

Solution Approach

Define State and Transition

Use a DP array where dp[i][j] represents the number of ways to form strings of length i with j letters matching the prefix of "leet". Each character extends partial matches, updating states according to the next required letter in "leet".

Iterate and Update Counts

Loop through all positions up to n, adding each possible letter and updating DP states. Track transitions carefully to avoid double-counting and ensure that sequences can eventually form "leet" through rearrangement.

Apply Combinatorial Multiplication

Once DP is complete, calculate combinations for extra letters beyond the four required for "leet". Multiply by factorial arrangements for repeated letters and take modulo 10^9 + 7 to produce the final count.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: 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)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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)

Solution 2: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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)

Continue Practicing

#3154 find number of ways to reach the k th stair #3250 find the count of monotonic pairs i #3251 find the count of monotonic pairs ii