Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math · Dynamic Programming
4
10
count-vowels-permutation)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2930: Number of Strings Which Can Be Rearranged to Contain Substring
class Solution {
private final int mod = (int) 1e9 + 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;
}
}
// Accepted solution for LeetCode #2930: Number of Strings Which Can Be Rearranged to Contain Substring
func stringCount(n int) int {
const mod int = 1e9 + 7
f := make([][2][3][2]int, n+1)
for i := range f {
for j := range f[i] {
for k := range f[i][j] {
for l := range f[i][j][k] {
f[i][j][k][l] = -1
}
}
}
}
var dfs func(i, l, e, t int) int
dfs = func(i, l, e, t int) int {
if i == 0 {
if l == 1 && e == 2 && t == 1 {
return 1
}
return 0
}
if f[i][l][e][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))
f[i][l][e][t] = (a + b + c + d) % mod
}
return f[i][l][e][t]
}
return dfs(n, 0, 0, 0)
}
# Accepted solution for LeetCode #2930: Number of Strings Which Can Be Rearranged to Contain Substring
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)
// Accepted solution for LeetCode #2930: Number of Strings Which Can Be Rearranged to Contain Substring
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #2930: Number of Strings Which Can Be Rearranged to Contain Substring
// class Solution {
// private final int mod = (int) 1e9 + 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;
// }
// }
// Accepted solution for LeetCode #2930: Number of Strings Which Can Be Rearranged to Contain Substring
function stringCount(n: number): number {
const mod = 10 ** 9 + 7;
const f: number[][][][] = Array.from({ length: n + 1 }, () =>
Array.from({ length: 2 }, () =>
Array.from({ length: 3 }, () => Array.from({ length: 2 }, () => -1)),
),
);
const dfs = (i: number, l: number, e: number, t: number): number => {
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];
}
const a = (dfs(i - 1, l, e, t) * 23) % mod;
const b = dfs(i - 1, Math.min(1, l + 1), e, t);
const c = dfs(i - 1, l, Math.min(2, e + 1), t);
const d = dfs(i - 1, l, e, Math.min(1, t + 1));
return (f[i][l][e][t] = (a + b + c + d) % mod);
};
return dfs(n, 0, 0, 0);
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.