<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:
    bool hasAllCodes(string s, int k) {
        int n=pow(2,k);      //for k ther will be 2^k possible binary codes
        vector<int> v(n,0);    //Initialise with zero , change 0 to 1 if this binary code is present in the string
        
        int m=s.length();
        if(k>m) return false;
        
        vector<int> hash(m-(k-1),0);        //to store hash value of all substring of size k
        
        for(int i=0;i<m-(k-1);i++)
        {
            //We have to calculate the value of fisrt binary number of length k
            
            if(i==0)
            {
                for(int j=0;j<k;j++)
                {
                    hash[0]=((hash[0]<<1)+int(s[j]-'0'));
                }
            }
            //after that we  will just remove leftmost digit and add a digit to right
            else
            {
                hash[i]=hash[i-1]-(hash[i-1]&(1<<k-1));
                hash[i]=hash[i]<<1;
                hash[i]+=int(s[i+k-1]-'0'); 
            }
        }
        
        for(int i=0;i<m-(k-1);i++)
        {
            v[hash[i]]=1;
        }
        for(int i=0;i<n;i++)
        {
            if(v[i]) continue;
            return false;
        }
        return true;
    }
};
72984