[C++] O(log n) 0ms Solution Using pow() Inclusion Exclusion Principle
Intuition\n Describe your first thoughts on how to solve this problem. \n### inclusion exclusion principle\n# Approach\n Describe your approach to solving the p
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n### inclusion exclusion principle\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBy looking at the substring "leet", we can observe that it contains only one \'l\', two \'e\', ans one \'t\'.\nFor this problem, we simply need to exclude all the strings that does not meet the requirement.\nThat is, the string that either contains no \'l\', or no \'t\', or less than two \'e\'.\n\nLet A, B, C, D be four events.\nA = strings that have zero \'l\'\nB = strings that have zero \'e\'\nC = strings that have one \'e\'\nD = strings that have zero \'t\'\n\nWe are going to find P(A\u222AB\u222AC\u222AD)\nNote that P(B\u2229C) = 0 because a string cannot have both one \'e\' and zero \'e\'\n\nUsing the inclusion exclusion principle, we can derive:\nP(A\u222AB\u222AC\u222AD) = P(A) + P(B) + P(C) + P(D) - P(A\u2229B) - P(A\u2229C) - P(A\u2229D) - P(B\u2229C) - P(B\u2229D) - P(C\u2229D) + P(A\u2229B\u2229C) + P(A\u2229B\u2229D) + P(A\u2229C\u2229D) + P(B\u2229C\u2229D) - P(A\u2229B\u2229C\u2229D)\n\nWe can remove any term with "B\u2229C", therefore:\n\nP(A\u222AB\u222AC\u222AD) = P(A) + P(B) + P(C) + P(D) - P(A\u2229B) - P(A\u2229C) - P(A\u2229D) - P(B\u2229D) - P(C\u2229D) + P(A\u2229B\u2229D) + P(A\u2229C\u2229D)\n\nThe rest shouldn\'t be too hard to figure out\n\nFor example:\n\nP(C) = n * pow(25, n - 1)\nthis means we can choose one out of n indices to be \'e\', and the rest are just arbitrary characters other than \'e\'\n\nP(A\u2229C) = n * pow(24, n - 1)\nwe can choose one out of n indices to be \'e\', and the rest are other characters other than \'l\' and \'e\', that is, 24 characters, so 24^(n - 1) ways to make the remaing string\n\n\n# Complexity\n- Time complexity: $$O(logN)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    const int mod = 1e9 + 7;\npublic:\n    int stringCount(int n) {\n        long long ans = 0;\n        // P(A) + P(B) + P(D)\n        ans += pow(25, n) * 3;\n        // P(C)\n        ans += pow(25, n - 1) * n;\n        // P(A\u2229B) + P(A\u2229D) + P(B\u2229D)\n        ans -= pow(24, n) * 3;\n        // P(A\u2229C) + P(C\u2229D)\n        ans -= pow(24, n - 1) * n * 2;\n        // P(A\u2229B\u2229D)\n        ans += pow(23, n);\n        // P(A\u2229C\u2229D)\n        ans += pow(23, n - 1) * n;\n        ans = pow(26, n) - ans;\n        return (ans % mod + mod) % mod;\n    }\n    \n    long long pow(int x, int p) {\n        long long res = 1;\n        for (; p; p >>= 1) {\n            if (p & 1) res = res * x % mod;\n            x = (long long)x * x % mod;\n        }\n        return res;\n    }\n};\n```
['Math', 'Combinatorics', 'C++']