Sliding Window Technique - Part 2

Crossing the 650 problems solved milestone today (weekends in covid-filled era are great for practicing algorithms)

Here is the 650th problem: https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/

1461. Check If a String Contains All Binary Codes of Size K

Medium

Given a binary string s and an integer k.

Return True if any binary code of length k is a substring of s. Otherwise, return False.

 

Example 1:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indicies 0, 1, 3 and 2 respectively.

Example 2:

Input: s = "00110", k = 2
Output: true

Example 3:

Input: s = "0110", k = 1
Output: true
Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring. 

Example 4:

Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and doesn't exist in the array.

Example 5:

Input: s = "0000000001011100", k = 4
Output: false

 

Constraints:

• 1 <= s.length <= 5 * 10^5
• s consists of 0's and 1's only.
• 1 <= k <= 20

Accepted

4,299

Submissions

12,166

At first it looks a little daunting - generate all the 2^k possibilities and look each one up on the string of len |s|? That would bring the total execution time to 2^k * |s|, which would be in the worst case 2^20 * 5 * 10^5, or this: 524,288,000,000. You don't want that.

Instead, use the Sliding Window technique as shown in a previous post: as you traverse the string, for each window of size k, take that sub-string and insert into a hash table. At the end, if the hash table contains 2^k entries, you should return true (false otherwise). Brings the complexity down to |s|, much more reasonable. Code is below, cheers, ACC.

public class Solution

{

    public bool HasAllCodes(string s, int k)

    {

        if (String.IsNullOrEmpty(s)) return false;

        Hashtable code = new Hashtable();

        int target = (int)Math.Pow(2, k);

        string c = "";

        for (int i = 0; i < s.Length; i++)

        {

            c += s[i].ToString();

            if (i >= k)

            {

                c = c.Substring(1);

            }

            if (c.Length == k)

            {

                if (!code.ContainsKey(c))

                {

                    code.Add(c, true);

                    if (code.Count == target) return true;

                }

            }

        }

        return code.Count == target;

    }

}