Time O(log(n)) - Combinatorics solution with explanation
Intuition\n\nThere are $26^n$ ways to create an abitrary string containing $26$ lowercase English letters. To count $n$- letter good strings, we find the number
# Intuition\n\nThere are $26^n$ ways to create an abitrary string containing $26$ lowercase English letters. To count $n$- letter good strings, we find the number of $n$- letter non-good string.\n\nLet:\n- $A$ be the set of $n$- letter strings having **no** letter `l`\n- $B$ be the set of $n$- letter strings having **no** letter `t`\n- $C$ be the set of $n$- letter strings having **at most** $1$ letter `e`\n\nTherefore, $A \\cup B \\cup C$ is the set of $n$- letter non-good strings.\n\nAccording to the **Principle of Inclusion - Exclusion**:\n$\\left|A\\cup B\\cup C\\right|=\\left|A\\right|+\\left|B\\right|+\\left|C\\right|-\\left|A\\cap B\\right|-\\left|B\\cap C\\right|-\\left|C\\cap A\\right|+\\left|A\\cap B\\cap C\\right|$\n\nNow, we will calculate the value of each terms in the right-hand side.\n\n1. Find $\\left|A\\right|$\nThere are $25$ ways to choose a letter for each index in a string in $A$ (as `l` is excluded), so there are $25^n$ ways to create a string in $A$. In other words, $\\left|A\\right|=25^n$.\n\n2. Find $\\left|B\\right|$\nSimilar to section 1, we can prove that $\\left|B\\right|=25^n$.\n\n3. Find $\\left|C\\right|$\nIf there is no letter `e`, similar to section 1, there are $25^n$ strings like that.\nIf there is exactly $1$ letter `e`, there is $n$ way to choose the index of letter `e` in the string. For the other indices, there are $25$ ways to choose a letter for each of them. Totally, there are $n\\cdot25^{n-1}$ ways to generate a string with exactly $1$ letter `e`.\nHence, $\\left|C\\right|=25^n+n\\cdot25^{n-1}$.\n\n4. Find $\\left|A\\cap B\\right|$\n$A\\cap B$ is the set of strings having no letter `l` and no letter `t`.\nTherefore, there are $24$ ways to choose a letter for each index. Totally, there are $24^n$ ways to generate strings in $A\\cap B$. In other words, $\\left|A\\cap B\\right|=24^n$\n\n5. Find $\\left|A\\cap C\\right|$\n$A\\cap B$ is the set of strings having no letter `l` and at most $1$ letter `e`.\nIf there is no letter `e`, similar to section 4, $\\left|A\\cap C\\right|=24^n$\nIf there is exactly $1$ letter `e`, there are $n$ ways to choose the index of letter `e`. For the other indices, there are $24$ ways to choose a letter for each of them. Totally, there are $n\\cdot 24^{n-1}$ ways to generate a string with $1$ letter `e` and no letter .\nTotally, $\\left|A\\cap C\\right|=24^n+n\\cdot 24^{n-1}$\n\n6. Find $\\left|B\\cap C\\right|$\n$A\\cap B$ is the set of strings having no letter `t` and at most $1$ letter `e`.\nSimilar to section 5, we can prove that $\\left|B\\cap C\\right|=24^n+n\\cdot 24^{n-1}$\n\n7. Find $\\left|A\\cap B\\cap C\\right|$\n$A\\cap B\\cap C$ is the set of strings with no letter `l` or `t`, and at most $1$ letter `e`.\nIf there is no letter `e`, there are $23$ ways to choose a letter for each index in a string. Therefore, there are $23^n$ ways to generate a string like that.\nIf there is exactly $1$ letter `e`, there are $n$ ways to choose the index of letter `e`. For the other indices, there are $23$ ways to choose a letter for each of them. Totally, there are $n\\cdot 23^{n-1}$ ways to generate a string with $1$ letter `e` and no letter `l` or `t`.\nTotally, $\\left|A\\cap C\\right|=23^n+n\\cdot 23^{n-1}$\n\n$\\Rightarrow\\left|A\\cup B\\cup C\\right|=25^{n-1}(75+n)-24^{n-1}(72+2n)+23^{n-1}(23+n)$\n\n***Hence, the number of $n$- letter good string is:***\n$\\boxed{26^n-25^{n-1}(75+n)+24^{n-1}(72+2n)-23^{n-1}(23+n)}$\n\n---\n# Approach\nDenote `mod=10**9+7`, then return the resultant expression we found above.\n\n---\n# Complexity\n- ### Time complexity: $O(\\log{n})$\n\n- ### Space complexity: $O(1)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n---\n# Code\n```Python3 []\nmod=10**9+7\nclass Solution:\n    def stringCount(self, n: int) -> int:    \n        return (pow(26,n,mod)-pow(25,n-1,mod)*(75+n)+pow(24,n-1,mod)*(2*n+72)-pow(23,n-1,mod)*(n+23))%mod\n```\n\n---\n## Postscript\nThis is my first time to write a solution on Leetcode. If you find something wrong or not accurate in my post, don\'t hesitate to comment. Thank you!
['Math', 'Divide and Conquer', 'Combinatorics', 'Python3']