title
给你一个整数 n 。
如果一个字符串 s 只包含小写英文字母，且 将 s 的字符重新排列后，新字符串包含 子字符串 "leet" ，那么我们称字符串 s 是一个 好 字符串。
比方说：
- 字符串
"lteer"是好字符串，因为重新排列后可以得到"leetr"。 "letl"不是好字符串，因为无法重新排列并得到子字符串"leet"。
请你返回长度为 n 的好字符串 总 数目。
由于答案可能很大，将答案对 109 + 7 取余 后返回。
子字符串 是一个字符串中一段连续的字符序列。
示例 1：
输入：n = 4
输出：12
解释：总共有 12 个字符串重新排列后包含子字符串 "leet" ："eelt" ，"eetl" ，"elet" ，"elte" ，"etel" ，"etle" ，"leet" ，"lete" ，"ltee" ，"teel" ，"tele" 和 "tlee" 。
示例 2：
输入：n = 10
输出：83943898
解释：长度为 10 的字符串重新排列后包含子字符串 "leet" 的方案数为 526083947580 。所以答案为 526083947580 % (109 + 7) = 83943898 。
提示：
1 <= n <= 105
solution
计数，每个状态统计了l,e,t的数量。DP.
Each loop, try 26 lowercase characters.
Another solution: Use Math. O(1), inclusion-exclusion principle 容斥原理。
MOD = int(1e9 + 7)
INF = float('inf')
class Solution:
def stringCount(self, n: int) -> int:
dp = collections.defaultdict(int)
dp[(0, 0, 0)] = 1
# l,e,t
for i in range(n):
ndp = collections.defaultdict(int)
for l in range(0, 2):
for e in range(0, 3):
for t in range(0, 2):
dp[(l, e, t)] %= MOD
ndp[(min(1, l + 1), e, t)] += dp[(l, e, t)]
ndp[(l, min(2, e + 1), t)] += dp[(l, e, t)]
ndp[(l, e, min(1, t + 1))] += dp[(l, e, t)]
ndp[(l, e, t)] += 23 * dp[(l, e, t)]
dp = ndp
# print(i, dp)
return dp[(1, 2, 1)] % MOD