<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 = s.size();
        // If k is greater than the length of the string, it's impossible to have all codes
        if (k > n) return false;

        int i = 0, j = 0;  // i is the start, j is the end of the window
        unordered_set<string> st;  // Set to store unique binary substrings of length k
        string ans = "";  // String to represent the current window
        
        // Traverse the string
        while (j < n) {
            // Add the current character to the window
            ans += s[j];

            // If the current window size is less than k, keep expanding it
            if (j - i + 1 < k) {
                j++;
            }
            // If the window size is exactly k
            else if (j - i + 1 == k) {
                // Insert the current window (substring) into the set
                st.insert(ans);

                // Remove the first character of the window to slide it
                ans.erase(0, 1);

                // Move both i and j to the right
                i++;
                j++;
            }
        }

        // We need 2^k unique binary codes of length k
        // Check if the set size is equal to 2^k
        return st.size() == pow(2,k);  // (1 << k) is the same as pow(2, k)
    }
};

114859