# Number of Strings Which Can Be Rearranged to Contain Substring
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-strings-which-can-be-rearranged-to-contain-substring)
Canonical: https://scaleengineer.com/dsa/problems/number-of-strings-which-can-be-rearranged-to-contain-substring
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
---
## Problem
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`

# Approaches
## Dynamic Programming
This approach involves building the strings of length `n` incrementally while keeping track of the necessary character counts. We define a state based on whether we have seen at least one 'l', at least one 't', and how many 'e's we've seen (0, 1, or 2+).
**Time:** O(n). The main loop runs `n` times, and inside the loop, we perform a constant number of operations (12 states * 4 transitions). · **Space:** O(1). We use two DP tables of size `2 * 3 * 2`, which is constant space.
**Pros:** More intuitive than combinatorics if you are familiar with DP.; Handles state transitions explicitly and is generally easier to debug.
**Cons:** Less efficient than the combinatorics approach, with a time complexity linear in `n`.
### Explanation
We use a dynamic programming table, `dp[l_flag][e_count][t_flag]`, to store the number of strings of a certain length that satisfy a specific state. The state is defined by three parameters:

- `l_flag`: 0 if no 'l' has been used, 1 if at least one 'l' has been used.
- `e_count`: The number of 'e's used, capped at 2 (i.e., states are 0, 1, or >=2).
- `t_flag`: 0 if no 't' has been used, 1 if at least one 't' has been used.

The DP table size is `2 x 3 x 2`, which is constant. We can optimize space by only storing the counts for the current length, as the counts for length `i` only depend on length `i-1`.

All calculations are performed modulo `10^9 + 7`.

```java
class Solution {
    public int stringCount(int n) {
        long MOD = 1_000_000_007;
        if (n < 4) return 0;

        // dp[l_flag][e_count][t_flag]
        long[][][] dp = new long[2][3][2];
        dp[0][0][0] = 1; // For the empty string

        for (int i = 0; i < n; i++) {
            long[][][] newDp = new long[2][3][2];
            for (int l = 0; l < 2; l++) {
                for (int e = 0; e < 3; e++) {
                    for (int t = 0; t < 2; t++) {
                        if (dp[l][e][t] == 0) continue;
                        long ways = dp[l][e][t];

                        // Case 1: Append 'l'
                        newDp[1][e][t] = (newDp[1][e][t] + ways) % MOD;

                        // Case 2: Append 'e'
                        newDp[l][Math.min(2, e + 1)][t] = (newDp[l][Math.min(2, e + 1)][t] + ways) % MOD;

                        // Case 3: Append 't'
                        newDp[l][e][1] = (newDp[l][e][1] + ways) % MOD;

                        // Case 4: Append any other character (26 - 3 = 23 choices)
                        newDp[l][e][t] = (newDp[l][e][t] + ways * 23) % MOD;
                    }
                }
            }
            dp = newDp;
        }

        return (int) dp[1][2][1];
    }
}
```
### Algorithm
- Define a DP state `dp[l_flag][e_count][t_flag]` to count strings based on the required character counts.
- The state parameters are:
  - `l_flag`: 0 for no 'l's, 1 for at least one 'l'.
  - `e_count`: 0, 1, or 2, representing the count of 'e's (capped at 2).
  - `t_flag`: 0 for no 't's, 1 for at least one 't'.
- Initialize a DP table `dp[2][3][2]` with `dp[0][0][0] = 1` (for the empty string) and all other states as 0.
- Iterate from `i = 1` to `n` to build strings of increasing length.
- In each iteration, compute a `new_dp` table for length `i` based on the `dp` table for length `i-1`.
- The transitions are calculated by considering appending a character ('l', 'e', 't', or one of the 23 others) to the strings of the previous length.
- After `n` iterations, the answer is the value in the state that meets all conditions, which is `dp[1][2][1]`.

## Combinatorics with Principle of Inclusion-Exclusion
This is a highly efficient mathematical approach. Instead of counting the 'good' strings directly, we calculate the total number of possible strings of length `n` and subtract the number of 'bad' strings. A string is 'bad' if it's not 'good', meaning it doesn't have the required characters to form 'leet' after rearrangement.
**Time:** O(log n). The complexity is dominated by the modular exponentiation calls, each taking `O(log n)` time. We make a constant number of such calls. · **Space:** O(1) (or O(log n) if the `power` function uses recursion, which can be implemented iteratively to be O(1)).
**Pros:** Extremely efficient, with a logarithmic time complexity.; Provides a closed-form mathematical solution that is independent of `n`'s magnitude.
**Cons:** Requires knowledge of combinatorics, specifically the Principle of Inclusion-Exclusion.; The formula can be complex to derive and prone to errors.
### Explanation
A string is 'good' if it has at least one 'l', at least two 'e's, and at least one 't'. A string is 'bad' if it violates at least one of these conditions. We can count the number of bad strings using the Principle of Inclusion-Exclusion (PIE).

Let's define the sets of bad strings:
- `A`: Set of strings with `count('l') == 0`.
- `B`: Set of strings with `count('e') <= 1`.
- `C`: Set of strings with `count('t') == 0`.

The number of bad strings is `|A U B U C|`. We calculate this by finding the sizes of the sets and their intersections:

- `|A| = |C| = 25^n`
- `|B| = 25^n + n * 25^(n-1)`
- `|A ∩ C| = 24^n`
- `|A ∩ B| = |B ∩ C| = 24^n + n * 24^(n-1)`
- `|A ∩ B ∩ C| = 23^n + n * 23^(n-1)`

We compute these values using modular exponentiation and combine them with the PIE formula. The final answer is `(Total Strings - Bad Strings) % MOD`.

```java
class Solution {
    long MOD = 1_000_000_007;

    public int stringCount(int n) {
        if (n < 4) {
            return 0;
        }

        long total = power(26, n);
        
        // Using PIE to find bad strings
        // A: count('l') = 0
        // B: count('e') <= 1
        // C: count('t') = 0
        
        // |A|, |C|
        long term1 = power(25, n);
        // |B|
        long term2 = (power(25, n) + (long)n * power(25, n - 1)) % MOD;
        
        // |A intersect C|
        long term12 = power(24, n);
        // |A intersect B|, |B intersect C|
        long term13 = (power(24, n) + (long)n * power(24, n - 1)) % MOD;
        
        // |A intersect B intersect C|
        long term123 = (power(23, n) + (long)n * power(23, n - 1)) % MOD;

        long badStrings = (2 * term1 + term2) % MOD;
        badStrings = (badStrings - (2 * term13 + term12)) % MOD;
        badStrings = (badStrings + term123) % MOD;

        long goodStrings = (total - badStrings) % MOD;
        
        // Handle negative result from modulo subtraction
        return (int)((goodStrings + MOD) % MOD);
    }

    private long power(long base, long exp) {
        if (exp < 0) return 0; // For n-1 cases where n=0
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
- Frame the problem as a complementary counting task. We find the total number of strings and subtract the 'bad' ones.
- The total number of strings of length `n` is `26^n`.
- A string is 'bad' if it has `count('l') < 1` OR `count('e') < 2` OR `count('t') < 1`.
- Define three sets for these conditions:
  - `A`: Strings with `count('l') = 0`.
  - `B`: Strings with `count('e') <= 1`.
  - `C`: Strings with `count('t') = 0`.
- Apply the Principle of Inclusion-Exclusion (PIE) to find the total number of bad strings: `|A U B U C| = |A| + |B| + |C| - (|A ∩ B| + |A ∩ C| + |B ∩ C|) + |A ∩ B ∩ C|`.
- Calculate the size of each set and their intersections using combinatorial formulas (e.g., `|A| = 25^n`, `|B| = 25^n + n * 25^(n-1)`).
- Use modular exponentiation to efficiently compute powers `a^b % MOD`.
- Subtract the count of bad strings from the total count to get the final answer.

# Solutions
### Java

```java
class Solution {
private
  final int mod = (int)1 e9 + 7;
private
  Long[][][][] f;
public
  int stringCount(int n) {
    f = new Long[n + 1][2][3][2];
    return (int)dfs(n, 0, 0, 0);
  }
private
  long dfs(int i, int l, int e, int t) {
    if (i == 0) {
      return l == 1 && e == 2 && t == 1 ? 1 : 0;
    }
    if (f[i][l][e][t] != null) {
      return f[i][l][e][t];
    }
    long a = dfs(i - 1, l, e, t) * 23 % mod;
    long b = dfs(i - 1, Math.min(1, l + 1), e, t);
    long c = dfs(i - 1, l, Math.min(2, e + 1), t);
    long d = dfs(i - 1, l, e, Math.min(1, t + 1));
    return f[i][l][e][t] = (a + b + c + d) % mod;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int stringCount(int n) {
    const int mod = 1e9 + 7;
    using ll = long long;
    ll f[n + 1][2][3][2];
    memset(f, -1, sizeof(f));
    function<ll(int, int, int, int)> dfs = [&](int i, int l, int e,
                                               int t) -> ll {
      if (i == 0) {
        return l == 1 && e == 2 && t == 1 ? 1 : 0;
      }
      if (f[i][l][e][t] != -1) {
        return f[i][l][e][t];
      }
      ll a = dfs(i - 1, l, e, t) * 23 % mod;
      ll b = dfs(i - 1, min(1, l + 1), e, t) % mod;
      ll c = dfs(i - 1, l, min(2, e + 1), t) % mod;
      ll d = dfs(i - 1, l, e, min(1, t + 1)) % mod;
      return f[i][l][e][t] = (a + b + c + d) % mod;
    };
    return dfs(n, 0, 0, 0);
  }
};

```

### Python

```python
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)

```