<p>Given a binary string <code>s</code> and an integer <code>k</code>, return <code>true</code> <em>if every binary code of length</em> <code>k</code> <em>is a substring of</em> <code>s</code>. Otherwise, return <code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;00110110&quot;, k = 2
<strong>Output:</strong> true
<strong>Explanation:</strong> The binary codes of length 2 are &quot;00&quot;, &quot;01&quot;, &quot;10&quot; and &quot;11&quot;. They can be all found as substrings at indices 0, 1, 3 and 2 respectively.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;0110&quot;, k = 1
<strong>Output:</strong> true
<strong>Explanation:</strong> The binary codes of length 1 are &quot;0&quot; and &quot;1&quot;, it is clear that both exist as a substring. 
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;0110&quot;, k = 2
<strong>Output:</strong> false
<strong>Explanation:</strong> The binary code &quot;00&quot; is of length 2 and does not exist in the array.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
	<li><code>1 &lt;= k &lt;= 20</code></li>
</ul>

class Solution {
public:
    /*
    Constraints:
        - 1 <= s.length <= 5 * 10^5
        - s[i] is either '0' or '1'.
        - 1 <= k <= 20
    
    The first thing to check is if k is too large given the length of s. The string s cannot contain unlimited substrings.
    It can contain:
    n substrings of size 1
    n-1 substring sf size 2
    n-(k-1) substrings of size k
    
    Once we confirm there are enough available sequences there are multiple options to find if we have all of them. A key point 
    to note is that we need 2^k differerent ones, of length k.
    
    - we can go from left to right and insert into a hash_set all the substrings of size k that we find. At the end there has to be 2^k
    - we can use a trie and count the leaves, there has to be 2^k leaves
    - we can use a rolling hash instead of the hash_st so it is faster to compute the hash
    
    */
    bool hasAllCodes(string s, int k) {
        
        int n=s.size();
        int total_needed = 1 << k; 
        int max_available = n-(k-1);
        if (total_needed > max_available)
            return false;
        
        // we can go over the string with a hash
        unordered_set<string> m;
        for(int i=0;i<n-k+1;++i) {
            string str = s.substr(i, k);
            m.insert(str);
        }
        return m.size() == total_needed;        
    }
};
106484