[PIE] Combinatorial solution (15ms)
We can solve the problem from backwards: Out of 26^n possible strings, how many of them cannot be arranged to have leet as a substring?\n\nLuckily, there are on
We can solve the problem from backwards: **Out of `26^n` possible strings, how many of them cannot be arranged to have `leet` as a substring?**\n\nLuckily, there are only 4 characters to worry about, so we can do some case work:\n- How many strings do not have the characters `e`, `l`, and `t`?\n- How many strings only have __one__ of the required characters? (`e`, `l`, and `t`)\n- How many strings have only __two__ of the required characters? (`le`, `lt`, and `et`)\n- How many strings can make `let`, **but not `leet`**?\n\nWe then combine all the above answers and take them away from `26^n`.\n\n### Only one required character\nSuppose we want to have `k` characters in a string of length `n` to be a particular character, we have `nCr(n, k)` choices to place the particular characters, and everything else is any character **except the required characters** (`23^(n-k)`).\n\n* Note: since we have 3 characters to worry about, we multiply the above answer by `3`.\n\n### Only two required characters\nPretend we have `k` spots again to fill in the two characters (both characters must appear once). **We only have to figure out how many ways to fill one character, because every other spot will be filled with the other character.** The number of ways to do so is `2^(k)-2` (`-2` at the end to remove the option to not take any spots and the option to take all the spots). We have 3 unique pairs of characters `le`, `lt`, `et`, so we multiply the answer by `3`.\n\n### Can make `let`, but not `leet`\nThis implies aside from having enough characters for `let`, we have as many `l` and `t` as we want, **without having another `e`!** For the final time, pretend we have `k` spots available. We know the character `e` takes one of those spots, so it has `k` spots it can pick from. Now, we just apply the above scenario with two characters, which are `l` and `t` **(do not multiply by `3` this time, that is the only pair of characters we can try now)**. \n\n```\ntemplate <int M> struct factorial {\n  vector<long long> fact, ifact, inv;\n  factorial(int n): fact(n + 1, 1), ifact(n + 1, 1), inv(n + 1, 1) {\n    for (int i = 2; i <= n; i++) {\n      fact[i] = fact[i - 1] * i % M;\n      inv[i] = 1LL * (M - M / i) * inv[M % i] % M;\n      ifact[i] = ifact[i - 1] * inv[i] % M;\n    }\n  }\n  long long ncr(int n, int k) {\n    return fact[n] * ifact[k] % M * ifact[n - k] % M;\n  }\n  long long npr(int n, int k) {\n    return fact[n] * ifact[n - k] % M;\n  }\n};\n\nclass Solution {\npublic:\n  int stringCount(int n) {\n    if (n < 4) return 0;\n    const int M = 1e9 + 7;\n    vector<long long> pow2(n + 1, 1), pow23(n + 1, 1); // precompute powers\n    for (int i = 1; i <= n; i++) {\n      pow2[i] = pow2[i - 1] * 2 % M;\n      pow23[i] = pow23[i - 1] * 23 % M;\n    }\n    factorial<M> f(n); // quickly compute nCr\n    long long ans = 1; // number of strings that cannot make "leet"\n    /* Case 1 */ for (int i = 0; i < n; i++) ans = ans * 23 % M;\n    /* Case 2 */ for (int i = 1; i <= n; i++) ans = (ans + f.ncr(n, i) * pow23[n - i] % M * 3 % M) % M;\n    /* Case 3 */ for (int i = 2; i <= n; i++)\n      ans = (ans + f.ncr(n, i) * ((pow2[i] + M - 2) % M) % M * pow23[n - i] % M * 3 % M) % M;\n    /* Case 4 */ for (int i = 3; i <= n; i++)\n      ans = (ans + f.ncr(n, i) * i % M * ((pow2[i - 1] + M - 2) % M) % M * pow23[n - i] % M) % M;\n    long long all = 1;\n    for (int i = 0; i < n; i++) all = all * 26 % M;\n    return (all + M - ans) % M; // PIE\n  }\n};\n```
['Math', 'Combinatorics', 'C++']