🔥✅ Most Optimized PnC Solution with Venn Diagram 🔥 | log(n) time, O(1) space
Intuition\n Describe your first thoughts on how to solve this problem. \nWe know that the total number of string with lenght n are: 26 n  as for each position w
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe know that the total number of string with lenght n are: 26<sup> n </sup> as for each position we have 26 options (a-z).\n_ _ _ _ ... _ [each _ can be filled with 26 options]\n\nSo `total` = 26 <sup>n</sup>\n\nNow we can find strings which cannot contain "leet" as substring even after rearranging.\nThe requrirements are:\n1. No \'l\' char\n2. No \'e\' or only one \'e\' char\n3. No \'t\' char\n\nSay the no of strings which doesn\'t contain "leet" be `sub`\n\nthen our result is, `res` = `total` - `sub`\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHow to find this number `sub`?\n\nWe first need to create a Venn diagram as show below:\n\n![image.png](https://assets.leetcode.com/users/images/b1f410d6-a6b0-4927-b0e5-d2731dd6c08c_1699718553.6400728.png)\n\n[Note: No \'e\' and One \'e\' will have no intersection]\n\nThe sum of all elements in this Venn diag will represent sub, and it will be given as:\n\n```\nsub = \n    No \'l\' + No \'e\' + No \'t\' + One \'e\' \n    - (No \'l\', \'e\') - (No \'e\', \'t\') - (No \'t\', \'l\') + ( No \'l\', \'t\', \'e\') \n    - (One \'e\' and No \'l\') - (One \'e\' and No \'t\') + (One \'e\' and No \'e\', \'t\') \n```\n\nWe just need to calculate these variables:\n- (No \'l\') = (No \'e\') = (No \'t\') = 25 <sup>n</sup>\n  Explanation: 25 options for each character\n- One \'e\' = 25 <sup>n-1</sup> * n \n  Explanation: 25 options for each character of n-1 length, then add e at any one of the n gaps between n-1 characters\n- (No \'l\', \'e\') = (No \'e\', \'t\') = (No \'t\', \'l\') = 24 <sup>n</sup>\n  Explanation: 24 options for each character\n- (No \'l\', \'t\', \'e\') = 23 <sup>n</sup>\n  Explanation: 23 options for each character\n- (One \'e\' and No \'l\') = (One \'e\' and No \'t\') = 24 <sup>n-1</sup> * n\n  Explanation: 25 options for each character of n-1 length, then add e at any one of the n gaps between n-1 characters\n- (One \'e\' and No \'e\', \'t\') = 23 <sup>n-1</sup> * n\n  Explanation: 23 options for each character of n-1 length, then add e at any one of the n gaps between n-1 characters\n\n# Complexity\n- Time complexity:\n$$O(log(n))$$\nUsing binary exponentiation we can calculate powers in $$log(n)$$ time\n\n- Space complexity:\n  $$O(1)$$\n  No extra space used\n\n# Code\n```\nclass Solution {\npublic:\n    const int MOD = 1e9 + 7;\n\n    int mod(long long num) {\n        return ((num % MOD) + MOD) % MOD;\n    }\n    \n    int add(int a, int b) {\n        return mod(a + b);\n    }\n    \n    int sub(int a, int b) {\n        return mod(a - b);\n    }\n    \n    int mul(int a, int b) {\n        long long res = 1LL * a * b;\n        return mod(res);\n    }\n\n    int binpower(int base, int e) {\n        int result = 1;\n        while (e) {\n            if (e & 1)\n                result = mul(result, base);\n            base = mul(base, base);\n            e >>= 1;\n        }\n        return result;\n    }\n    \n    int stringCount(int n) {\n        int total = binpower(26, n);\n        int NoL, NoE, NoT;\n        NoL = NoE = NoT = binpower(25, n);\n        int OneE = mul(binpower(25, n-1), n);\n        int NoLE, NoET, NoTL;\n        NoLE = NoET = NoTL = binpower(24, n);\n        int NoLTE = binpower(23, n);\n        int OneENoL, OneENoT;\n        OneENoL = OneENoT = mul(binpower(24, n-1), n);\n        int OneENoET = mul(binpower(23, n-1), n);\n        long long remove = 0LL + NoL + NoE + NoT + OneE - NoLE - NoET - NoTL + NoLTE - OneENoL - OneENoT + OneENoET;\n        remove = mod(remove);\n        return sub(total, remove);\n    }\n};\n```
['C++']