2931. Maximum Spending After Buying Items

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.

long long dp[101010][3][2][2];
class Solution {
    long long mod = 1e9 + 7;
    long long helper(int n, int e, int l, int t) {
        if(n == 0) return e == 0 and l == 0 and t == 0;
        long long& res = dp[n][e][l][t];
        if(res != -1) return res;
        res = helper(n-1,e,l,t) * (26 - (e > 0) - (l > 0) - (t > 0)) % mod;
        if(e) {
            res = (res + helper(n-1,e-1,l,t)) % mod;
        }
        if(l) {
            res = (res + helper(n - 1, e,l-1,t)) % mod;
        }
        if(t) {
            res = (res + helper(n-1, e, l, t-1)) % mod;
        }
        return res;
    }
public:
    int stringCount(int n) {
        memset(dp,-1,sizeof dp);
        return helper(n,2,1,1);
    }
};