C++ | Bitmask | DP
Intuition\nkeep track of e, l, t and see if I have already used \'e\' at least two times, \'l\' one time, and \'t\' one time using masking after finishing all m
# Intuition\nkeep track of e, l, t and see if I have already used \'e\' at least two times, \'l\' one time, and \'t\' one time using masking after finishing all my slots.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nUsing:\n1 as first \'e\'\n2 as second \'e\'\n4 as \'l\'\n8 as \'t\'\nbitmask all of them : (1 | 2 | 4 | 8 ) = 15\n\nRunning a loop in the dp function from 0 to 25 for every letter and check if (i==4) for \'e\', (i==11) for \'l\' and (i==19) for \'t\'.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n * 2^4 * 26)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n * 2^4)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    #define mod 1000000007\n    vector<vector<int>>dp;\n    int func(int n, int mask){\n        if(n==0){\n            if(mask==15) return 1;\n            return 0;\n        }\n        if(dp[n][mask]!=-1) return dp[n][mask];\n        int ans = 0;\n        for(int i=0; i<26; i++){\n            if(i==4){\n                if(mask&1) ans = (ans+func(n-1,(mask|2)))%mod;\n                else ans = (ans+func(n-1,(mask|1)))%mod;\n            }\n            else if(i==11) ans = (ans+func(n-1,(mask|4)))%mod;\n            else if(i==19) ans = (ans+func(n-1,(mask|8)))%mod;\n            else ans = (ans+func(n-1,mask))%mod;\n        }\n        return dp[n][mask] = ans;\n    }\n    int stringCount(int n) {\n        if(n<4) return 0;\n        dp.resize(n+1);\n        for(int i=0; i<=n; i++) dp[i].resize(16,-1);\n        return func(n,0);\n    }\n};\n```
['Dynamic Programming', 'Bitmask', 'C++']