Let $k>1$ be an integer, let $n = 2^k$. Let $s: \{0, \ldots, n-1\} \to \{0,1\}$ be any binary sequence of length $n = 2^k$. There are $n - k$ coherent subsequences of $s$ having length $k$, and the total number of binary sequence of length $k$ is $n=2^k$, so there are some binary sequences of length $k$ that are not a subsequence of $s$.
Question. Is there an algorithm with time $O(n)$ outputting one binary sequence of length $k$ that is not a subsequence of $s$?
Construct a suffix tree for your string. If your string contained all $2^k$ substrings of length $k$, then the first $k$ levels of the suffix tree, ignoring edges labelled \$, would be a complete binary tree, and moreover, in the first $k-1$ levels, all edge labels have length $1$. Since this is not the case, one of the following must happen:
Some edge label in the first $k-1$ levels has length more than $1$. Take such an edge label as high up in the tree as possible. In spells a substring $p$ of length at most $k$ which does occur in the word, but if we flip the final bit, then we get a substring $p'$ which doesn't.
All edge labels in the first $k-1$ levels have length exactly $1$. In that case, after removing edges labelled \$, the first $k$ levels cannot form a complete binary tree. In particular, some node, corresponding to a substring $p$ of length less than $k$, has a child whose label starts with $\sigma \neq \\\$$, but no child whose label starts with $\overline{\sigma}$. Thus $p\overline{\sigma}$ does not occur in the word.
Here is an example: Let $k = 2$, and consider the word $0011$.
After removing edges labeled \$, the root has two outoing edges labelled $0,1$; its $0$-child has two outgoing edges lablled $011\\\$$ and $11\\\$$; and its $1$-child has a single outgoing edge $1\\\$$. Thus the subtring $10$ is missing.
Here is another example: Again let $k=2$, and consider the word $0101$.
After removing edges labeled \$, the root has two outgoing edges labelled $01,1$. Thus the substring $00$ is missing. The $1$-child has a single outgoing edge labelled $01\\\$$, and so the substring $11$ is also missing.
