<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>

using ll = long long;
class Solution {
public:
    static const int base = 2;
    static const int maxn = 5 * 1e5 + 10;
    static const int MOD = 1e9 + 7;

    ll getHash(int l, int r, vector<ll> powers, vector<ll> hashs) {
        return (hashs[r] - (hashs[l - 1] * powers[r - l + 1]) % MOD + MOD) % MOD;
    }

    bool hasAllCodes(string s, int k) {
        int n = s.length();

        if (n < k) return false;

        vector<ll> powers(n + 1, 1);
        vector<ll> hashs(n + 1, 0);

        map<int, bool> hash_counter;

        for(int i = 1; i <= n; i++) {
            powers[i] = (powers[i - 1] * base) % MOD;
            hashs[i] = (hashs[i - 1] * base + (s[i - 1] - '0')) % MOD;
        }

        ll maxVal = pow(2, k);

        int sz=pow(2,k); //0 se leke 2^k-1 tak ke number honge  00 01 10 11 (3)
        //generate all hashcodes of len=k
        unordered_map<int,int> mp;
        int hash=0;
       for(int i=0;i<k;i++)
       {
           hash=hash*2+s[i]-'0';
       }
        int val=pow(2,k-1);
       for(int i=k;i<s.size();i++)
       {
            mp[hash]++;
            hash=(hash-(s[i-k]-'0')*(val))*2+s[i]-'0';
       }
       mp[hash]++;
       if(mp.size()==sz)
       return true;
       return false;
    }
};
100203