Algorithms
Medium
2930
3200
Number of Strings Which Can Be Rearranged to Contain Substring
number-of-strings-which-can-be-rearranged-to-contain-substring
"""
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
"""
class Solution:
    def stringCount(self, n: int) -> int:
        
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


Please complete the code below to solve above prblem:
```python
class Solution:
    def stringCount(self, n: int) -> int:
        
```

my_solution = Solution()

test_input = { "n": 4 }
assert my_solution.stringCount(**test_input) == 12

test_input = { "n": 10 }
assert my_solution.stringCount(**test_input) == 83943898

test_input = { "n": 1 }
assert my_solution.stringCount(**test_input) == 0

test_input = { "n": 2 }
assert my_solution.stringCount(**test_input) == 0

test_input = { "n": 3 }
assert my_solution.stringCount(**test_input) == 0

test_input = { "n": 5 }
assert my_solution.stringCount(**test_input) == 1460

test_input = { "n": 6 }
assert my_solution.stringCount(**test_input) == 106620

test_input = { "n": 7 }
assert my_solution.stringCount(**test_input) == 6058192

test_input = { "n": 8 }
assert my_solution.stringCount(**test_input) == 295164156

test_input = { "n": 9 }
assert my_solution.stringCount(**test_input) == 947613240

test_input = { "n": 11 }
assert my_solution.stringCount(**test_input) == 795234177

test_input = { "n": 12 }
assert my_solution.stringCount(**test_input) == 55396773

test_input = { "n": 13 }
assert my_solution.stringCount(**test_input) == 968092561

test_input = { "n": 14 }
assert my_solution.stringCount(**test_input) == 715599898

test_input = { "n": 15 }
assert my_solution.stringCount(**test_input) == 430509685

test_input = { "n": 16 }
assert my_solution.stringCount(**test_input) == 462719236

test_input = { "n": 17 }
assert my_solution.stringCount(**test_input) == 155543310

test_input = { "n": 18 }
assert my_solution.stringCount(**test_input) == 159683962

test_input = { "n": 19 }
assert my_solution.stringCount(**test_input) == 808507313

test_input = { "n": 20 }
assert my_solution.stringCount(**test_input) == 291395991

test_input = { "n": 21 }
assert my_solution.stringCount(**test_input) == 461951930

test_input = { "n": 22 }
assert my_solution.stringCount(**test_input) == 871561520

test_input = { "n": 23 }
assert my_solution.stringCount(**test_input) == 993268925

test_input = { "n": 24 }
assert my_solution.stringCount(**test_input) == 871982505

test_input = { "n": 25 }
assert my_solution.stringCount(**test_input) == 935610434

test_input = { "n": 26 }
assert my_solution.stringCount(**test_input) == 867518559

test_input = { "n": 27 }
assert my_solution.stringCount(**test_input) == 3067523

test_input = { "n": 28 }
assert my_solution.stringCount(**test_input) == 716801469

test_input = { "n": 29 }
assert my_solution.stringCount(**test_input) == 452206104

test_input = { "n": 30 }
assert my_solution.stringCount(**test_input) == 52805056

test_input = { "n": 31 }
assert my_solution.stringCount(**test_input) == 61992724

test_input = { "n": 32 }
assert my_solution.stringCount(**test_input) == 76928250

test_input = { "n": 33 }
assert my_solution.stringCount(**test_input) == 257967635

test_input = { "n": 34 }
assert my_solution.stringCount(**test_input) == 549347744

test_input = { "n": 35 }
assert my_solution.stringCount(**test_input) == 290653839

test_input = { "n": 36 }
assert my_solution.stringCount(**test_input) == 123906995

test_input = { "n": 37 }
assert my_solution.stringCount(**test_input) == 41253530

test_input = { "n": 38 }
assert my_solution.stringCount(**test_input) == 828924891

test_input = { "n": 39 }
assert my_solution.stringCount(**test_input) == 60893212

test_input = { "n": 40 }
assert my_solution.stringCount(**test_input) == 618599272

test_input = { "n": 41 }
assert my_solution.stringCount(**test_input) == 840600409

test_input = { "n": 42 }
assert my_solution.stringCount(**test_input) == 995406621

test_input = { "n": 43 }
assert my_solution.stringCount(**test_input) == 991833054

test_input = { "n": 44 }
assert my_solution.stringCount(**test_input) == 403185520

test_input = { "n": 45 }
assert my_solution.stringCount(**test_input) == 904195428

test_input = { "n": 46 }
assert my_solution.stringCount(**test_input) == 643609894

test_input = { "n": 47 }
assert my_solution.stringCount(**test_input) == 177947842

test_input = { "n": 48 }
assert my_solution.stringCount(**test_input) == 826753905

test_input = { "n": 49 }
assert my_solution.stringCount(**test_input) == 855443295

test_input = { "n": 50 }
assert my_solution.stringCount(**test_input) == 232825199

test_input = { "n": 51 }
assert my_solution.stringCount(**test_input) == 227116084

test_input = { "n": 52 }
assert my_solution.stringCount(**test_input) == 417264566

test_input = { "n": 53 }
assert my_solution.stringCount(**test_input) == 468973861

test_input = { "n": 54 }
assert my_solution.stringCount(**test_input) == 999145386

test_input = { "n": 55 }
assert my_solution.stringCount(**test_input) == 721276317

test_input = { "n": 56 }
assert my_solution.stringCount(**test_input) == 385673910

test_input = { "n": 57 }
assert my_solution.stringCount(**test_input) == 7891114

test_input = { "n": 58 }
assert my_solution.stringCount(**test_input) == 85081065

test_input = { "n": 59 }
assert my_solution.stringCount(**test_input) == 194677227

test_input = { "n": 60 }
assert my_solution.stringCount(**test_input) == 759126147

test_input = { "n": 61 }
assert my_solution.stringCount(**test_input) == 273111337

test_input = { "n": 62 }
assert my_solution.stringCount(**test_input) == 166598301

test_input = { "n": 63 }
assert my_solution.stringCount(**test_input) == 955460796

test_input = { "n": 64 }
assert my_solution.stringCount(**test_input) == 685704195

test_input = { "n": 65 }
assert my_solution.stringCount(**test_input) == 821093882

test_input = { "n": 66 }
assert my_solution.stringCount(**test_input) == 172674695

test_input = { "n": 67 }
assert my_solution.stringCount(**test_input) == 464621746

test_input = { "n": 68 }
assert my_solution.stringCount(**test_input) == 432202634

test_input = { "n": 69 }
assert my_solution.stringCount(**test_input) == 465445347

test_input = { "n": 70 }
assert my_solution.stringCount(**test_input) == 654273613

test_input = { "n": 71 }
assert my_solution.stringCount(**test_input) == 366864502

test_input = { "n": 72 }
assert my_solution.stringCount(**test_input) == 124689502

test_input = { "n": 73 }
assert my_solution.stringCount(**test_input) == 419691288

test_input = { "n": 74 }
assert my_solution.stringCount(**test_input) == 987033948

test_input = { "n": 75 }
assert my_solution.stringCount(**test_input) == 842828500

test_input = { "n": 76 }
assert my_solution.stringCount(**test_input) == 409614634

test_input = { "n": 77 }
assert my_solution.stringCount(**test_input) == 73844796

test_input = { "n": 78 }
assert my_solution.stringCount(**test_input) == 584672527

test_input = { "n": 79 }
assert my_solution.stringCount(**test_input) == 113476429

test_input = { "n": 80 }
assert my_solution.stringCount(**test_input) == 974106352

test_input = { "n": 81 }
assert my_solution.stringCount(**test_input) == 646239862

test_input = { "n": 82 }
assert my_solution.stringCount(**test_input) == 420253116

test_input = { "n": 83 }
assert my_solution.stringCount(**test_input) == 817573615

test_input = { "n": 84 }
assert my_solution.stringCount(**test_input) == 471199144

test_input = { "n": 85 }
assert my_solution.stringCount(**test_input) == 567239979

test_input = { "n": 86 }
assert my_solution.stringCount(**test_input) == 221534816

test_input = { "n": 87 }
assert my_solution.stringCount(**test_input) == 707218848

test_input = { "n": 88 }
assert my_solution.stringCount(**test_input) == 687360104

test_input = { "n": 89 }
assert my_solution.stringCount(**test_input) == 551986596

test_input = { "n": 90 }
assert my_solution.stringCount(**test_input) == 122933939

test_input = { "n": 91 }
assert my_solution.stringCount(**test_input) == 427294641

test_input = { "n": 92 }
assert my_solution.stringCount(**test_input) == 14022454

test_input = { "n": 93 }
assert my_solution.stringCount(**test_input) == 568729284

test_input = { "n": 94 }
assert my_solution.stringCount(**test_input) == 653568519

test_input = { "n": 95 }
assert my_solution.stringCount(**test_input) == 15509440

test_input = { "n": 96 }
assert my_solution.stringCount(**test_input) == 991824044

test_input = { "n": 97 }
assert my_solution.stringCount(**test_input) == 690441338

test_input = { "n": 98 }
assert my_solution.stringCount(**test_input) == 600462833

test_input = { "n": 99 }
assert my_solution.stringCount(**test_input) == 880019356

test_input = { "n": 100 }
assert my_solution.stringCount(**test_input) == 86731066