Enhancing this turing machine's runtime
There is a Turing machine operating in time $n + 1$ or so, but with lots of states. The machine simulates a DFA for your language. It has $O(2^k)$ states which "remember" the last $k$ characters.