Inclusion - Exclusion Principle | Math | Easy to Understand | C++ | TC: O(logn) | Beat 100%
The basic idea is to calculate the Number of strings of length n containing at least one l and one t and subtract from it the Number of strings of length n cont
The basic idea is to calculate the ```Number of strings of length n containing at least one l and one t``` and subtract from it the ```Number of strings of length n containg either 0 or 1 e and at least one l and one t```\nLet us find anwer to these separately: \n1) ```Number of strings of length n containing at least one l and one t```:\nThis equals to \n```Total number of strings of length n - Total number of strings of length n without either l or t```\nNow,\n```Total number of strings of length n``` : equals to ```26^n``` ( as we have to fill n places and have 26 options for each place ).\n```Total number of strings of size n without either l or t : Number of strings without l + Number of strings without t - Number of strings without both l and t```\nThe last term is subtracted as it has been counted twice earlier in the former two terms ( namely ```Number of strings without l , Number of strings without t``` )\n```Number of strings without l = 25^n``` as we have ```25``` choices for n places ( since we cannot use ```l``` )\nSimilarly, ```Number of strings without t = 25^n```\nand ```Number of strings without both l, t = 24^n```\nSo first part of our answer is ```26^n - 2 * 25^n + 24^n```\n\n2) ```Number of strings containg no e and at least one l and one t```:\nEverything else is same as ```1)```, with only one difference, the we have **one letter less to work with than before** , so the base numbers in ```1)``` will just subtract by ```1``` here\n```25^n - 2 * 24^n + 23^n```\n3) ```Number of strings containg either one e and at least one l and one t```\nFirst let us put the ```e``` at some position, we have ```n``` choices for that. And for each such choice we will have to find the rest of the characters, which is equal to finding ```number of strings of length n-1 containg zero e and at least one l and one t```, which is basically ```2)``` with string length ```n-1```\nSo answer : ```n * ( 25^(n-1) - 2 * 24^(n-1) + 23^(n-1) )```\n**Final answer:** ```1) - 2) - 3)```, as discussed in the beginning.\nCode:\n```\nclass Solution {\npublic:\nlong long power(long long x, long long y, long long p) \n{ \n    long long res = 1;\n    x = x % p;\n    if (x == 0) return 0;\n    while (y > 0) \n    { \n        if (y & 1) \n            res = (res*x) % p; \n        y = y>>1;\n        x = (x*x) % p; \n    } \n    return res; \n} \n \n    int stringCount(int n) {\n        long long mod=1e9+7;\n        if(n<4) return 0;\n        return ((power(26,n,mod)-2*power(25,n,mod)+power(24,n,mod)-1*power(25,n,mod)+2*power(24,n,mod)-1*power(23,n,mod)+n*(-1*power(25,n-1,mod)+2*power(24,n-1,mod)-1*power(23,n-1,mod)))%mod+mod)%mod;\n    }\n};\n```
['Math', 'C']