We prove that a O(k \log k)-probe local algorithm for k-Missing String presented by Vyas and Williams is asymptotically optimal among a certain class of algorithms for this problem. The best lower bound we are aware of for the general case is still \Omega(k).