Your count is correct.
Now let us find the number of possibilities if our number starts with the same two digits OR ends with the same three digits. Again we assume that $0$ and $1$ are forbidden as first digit. But they may occur as second digit, for example in $506888$.
There are $(8)(10^4)$ numbers that begin with two equal digits, the first (and therefore second) digit being neither $0$ or $1$.
There are $(8)(10^3)$ numbers that start with an allowed digit and whose last three digits are the same.
If we add the two numbers above, we will have double-counted the numbers in which the first two digits are the same, and the last three are the same.
It follows that the required number is $(8)(10^4)+(8)(10^3)-(8)(10^2)$.
Remark: This is a relatively simple instance of a technique called Inclusion/Exclusion. There are more elaborate versions.