The first observation is that the answer can not be more than . This is becausd there are 2^k different possible substrings of length k, but only |S| - k + 1 of them can fit into the string S.

For each k between 1 and , you can record all length k substrings in S, put them all in a set and see which set is too small. Complexity is .

First, it is easy to see why the answer is not more than 18. Actually, it's not more than log2(|S|)+1.

Why? Let's call the answer is n. In order to be the smallest necessary length, the string must contain all the binary substring of length n-1. There are 2^(n-1) possibilities, so the length of S must at least of length 2^(n-1) + n — 2. And there's a well-known constructive algorithm which can generate the string satisfies the lower bound, using knowledge of graph and Euler Tour, which it's too long to write it here. But, we can definitely say that this is the true lower bound.

What's next? We can do the brute forces, and checking all the substrings using hash or some string suffix structure. The complexity is O(nlogn).

P/S: There may be some mistakes, like plus/minus 1, or worse, my arguments are wrong. Please tell me if you find anything. Thank you!