DP with Bitmasking
Complexity\n- Time complexity: O(n2616)\n- Space complexity: O(n*16)\n\nCredit : https://leetcode.com/tanvir03/\n\n# Code\n\nclass Solution {\npublic:\n    cons
# Complexity\n- Time complexity: $$O(n*26*16)$$\n- Space complexity: $$O(n*16)$$\n\nCredit : https://leetcode.com/tanvir03/\n\n# Code\n```\nclass Solution {\npublic:\n    const int mod = 1e9 + 7;\n    vector<vector<int>>dp;\n    int func(int n, int mask){\n        if(n==0) return mask == 15;\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    \n    int stringCount(int n) {\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++']