Bitmask DP Solution - Cpp, Java, Python
\n# Intuition\n Describe your first thoughts on how to solve this problem. \nSince we are allowed to rearrange the letters, we only need to make sure that we ar
\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSince we are allowed to rearrange the letters, we only need to make sure that we are choosing atleast one `l`, one `t` and two `e`\'s in our final string. We can maintain this information in a simple bit mask. All we need is 4 bits!\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- We can use dynamic programming to solve the problem. \n- We can represent our dp state as $(i, mask)$ where $i$ represents the index of the string and $mask$ stores which characters from the word `leet` we have chosen so far.\n- At every index, we have the following choices:\n    - Choose `l`.\n    - Choose `t`.\n    - Choose `e`. When we choose `e`, we need to keep track of whether we are choosing the first or second `e`.\n    - Choose any of the other remaining characters.\n\n\n![LC-solution.png](https://assets.leetcode.com/users/images/f8e52ff1-d70a-4c97-b1fc-d99b68c78be5_1699863901.5617363.png)\n\n\n# Complexity\n- Time complexity: $O(n * 12)$\n    - This because count of `l` can be 0 or 1, count of `e` can be 0 or 1 or 2 and count of `t` can be 0 or 1. Hence, we have `2 * 2 * 3 = 12` possible states at each position.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(n * 16)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\n```python []\nclass Solution:\n    def stringCount(self, n: int) -> int:\n        MOD = 10 ** 9 + 7\n        \n        EMPTY = 0b0000\n        LEET = 0b1111\n        L = 0b1000\n        FIRST_E = 0b0100\n        SECOND_E = 0b0010\n        T = 0b0001\n\n        @cache\n        def dp(i = 0, mask = EMPTY):\n            if i == n:\n                return int(mask == LEET)\n                        \n            # Choose L or T\n            ways = dp(i + 1, mask | L) + dp(i + 1, mask | T)\n            \n            if mask & FIRST_E:\n                # FIRST_E was already chosen earlier\n                ways += dp(i + 1, mask | SECOND_E)\n            else:\n                # Choose FIRST_E\n                ways += dp(i + 1, mask | FIRST_E)\n            \n            # Choose any of other 23 chars\n            ways += 23 * dp(i + 1, mask)   \n\n            return ways % MOD\n        \n        return dp()\n```\n```cpp []\nenum Masks {\n    EMPTY = 0b0000,\n    LEET = 0b1111,\n    L = 0b1000,\n    FIRST_E =  0b0100,\n    SECOND_E = 0b0010,\n    T = 0b0001\n};\n\nusing ll = long long;\n\nclass Solution {\n    int n;\n    static const int MOD = 1e9 + 7;\n    vector<vector<ll>> dp;\n\npublic:\n    int stringCount(int n) {\n        this -> n = n;\n        this -> dp = vector<vector<ll>>(n, vector<ll>(16, -1));\n        return (int)findWays(0, EMPTY);\n    }\n\n    ll findWays(int i, int mask){\n        if(i == n)\n            return mask == LEET;\n\n        if(dp[i][mask] != -1)\n            return dp[i][mask];\n        \n        // Choose L or T\n        ll ways = findWays(i + 1, mask | L) + findWays(i + 1, mask | T);\n\n        if(mask & FIRST_E)\n            // FIRST_E was already chosen earlier\n            ways += findWays(i + 1, mask | SECOND_E);\n        else\n            // Choose FIRST_E\n            ways += findWays(i + 1, mask | FIRST_E);\n\n        // Choose any of other 23 chars\n        ways += (23ll * findWays(i + 1, mask)) % MOD;\n        return dp[i][mask] = ways % MOD;\n    }\n};\n```\n\n```java []\nclass Solution {\n    private static final int EMPTY = 0b0000,\n        LEET = 0b1111,\n        L = 0b1000,\n        FIRST_E =  0b0100,\n        SECOND_E = 0b0010,\n        T = 0b0001;\n    \n    private static final long MOD = 1_000_000_007;\n\n    private long dp[][], n;\n\n    public int stringCount(int n) {\n        this.n = n;\n        this.dp = new long[n][16];\n        for(int i = 0; i < n; i++){\n            Arrays.fill(dp[i], -1);\n        }\n        return (int)this.findWays(0, EMPTY);\n    }\n\n    long findWays(int i, int mask){\n        if(i == n)\n            return mask == LEET ? 1 : 0;\n\n        if(dp[i][mask] != -1)\n            return dp[i][mask];\n        \n        // Choose L or T\n        long ways = findWays(i + 1, mask | L) + findWays(i + 1, mask | T);\n\n        if((mask & FIRST_E) > 0)\n            // FIRST_E was already chosen earlier\n            ways += findWays(i + 1, mask | SECOND_E);\n        else\n            // Choose FIRST_E\n            ways += findWays(i + 1, mask | FIRST_E);\n\n        // Choose any of other 23 chars\n        ways = (ways + 23 * findWays(i + 1, mask)) % MOD;\n        \n        dp[i][mask] = ways;\n        return ways;\n    }\n}\n```\n\n#### Hope you have a great day! Do upvote if you like the solution!
['Dynamic Programming', 'Bitmask', 'C++', 'Java', 'Python3']