combinatorics - How many 6-letter strings contain neither the word 'bob' nor 'tim'

If I have a string that is 6-letters long and all lowercase letters, where letters can be repeated, how many strings contain neither the word bob nor tim?

Would I find the number of 6-letter strings that contain bob and the number of 6-letter strings contain tim separately then subtract their sum from the total number of strings possible?

Answer

First count the number of $6$-letter strings containing the substring "bob".

For $1\le k\le 4$, the number of $6$-letter strings that contain the substring "bob" at position $k$ is $26^3$, since the other $3$ positions can be freely chosen.

Thus, we have an initial count of $(4)(26^3) = 70304$.

But this is an overcount since those $6$-letter strings containing two occurrences of "bob" are counted twice.

If a $6$-letter string has two occurrences of "bob", it's either "bobbob" or else it has one of the forms "Xbobob", "bobobX", where "X" can be any character.

Thus, the number of $6$-letter strings containing two occurrences of "bob" is $1 + 26 + 26 = 53$, hence the corrected count for the number of $6$-letter strings containing the substring "bob" is $70304-53=70251$.

Next, count the number of $6$-letter strings containing the substring "tim".

The initial count is $(4)(26^3) = 70304$, the same as for the substring "bob".

But the overcount is just $1$, since the only $6$-letter string containing two occurrences of "tim" is "timtim".

Hence, the corrected count for the number of $6$-letter strings containing the substring "tim" is $70304-1=70303$.

It follows that the number of $6$-letter strings containing at least one of the substrings "bob" or "tim" is $70251+70303-2=140552$, where the subtraction of $2$ is to correct for the strings "bobtim" and "timbob", which were counted twice.

Finally, the number of $6$-letter strings not containing either of the substrings "bob" or "tim" is $26^6-140552=308775224$.