Leetcode: Check If a String Contains all Binary Codes of Size K

This question was asked at Google around 2 years ago. Here it is:

Given a binary string s and integer k, return true if every binary code of length k is a substring of s. Otherwise, return false. For example, if a string's length is k = 3, this means that 000, 001, 010, 011, 100, 101, 110, 111 are all inside of the substring. A false example is "0000000001011100" is false because it doesn't contain 1111. A true string is k = 2 at 00110110 because it has all of the strings "00", "01", "10", and "11", which are found in strings 0, 1, 3, 2. 

The hints are as follows:

1. We need only to check all substrings of length k. 

2. The number of distinct substrings should be 2^k so the time complexity should be O(2^k). 

We need to check every substring with length k until we get all of the possible binary codes. The 2 approaches to this are hash and set. The first implementation is O(2^k) which is a brute force implementation. 

class Solution {

    public boolean hasAllCodes(String s, int k) {

        //number of occurrences we need. Example: 100 k = 2.

        int need = 1 << k; 

        Set<String> got = new HashSet<String>();

        for(int i = k; i <= s.length(); i++) {

            //check the substring from the beginning to the end

            String a = s.substring(i - k, i);

            //decrement if there is a new substring

            if(!got.contains(a)) {

                got.add(a);

                need--;

            }

            //return true if we covered everything.

            if(need == 0) {

                return true;

            }

         }

    }

        return false;

    }

}

The next implementation uses Hash sets and Hash functions. 

Here we have at most 2^k strings, and we can map each string to a number in [0, 2^k - 1]. Each binary number has a unique hash value, and we can get the current hash from the last one, which you remove the most significant digit, then add a least significant digit to the bitwise operations. 

For this we shift right and get rid of the most significant digit, and or this with the least significant digit. It's a really elegant approach.

11010110 ---> 110 --> shift left --> 1100 --> discard first digit ---> 100 ---> or last digit ----> 100 | 1 = 101. 

This helps us go to O(N) optimized time complexity. 

Here's the final code: 

class Solution {

    public static boolean hasAllCodes(String s, int k) {

        int need = 1 << k;

        boolean[] got = new boolean[need];

        int allOne = need - 1;

        int hashVal = 0;

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

            //compute hash value shifting right, elegant solution.

            hashVal = ((hashVal << 1) & allOne) | (s.charAt(i) - '0');

            //see if we got the hash value

            if (i >= k - 1 && !got[hashVal]) {

                got[hashVal] = true;

                need--;

                //verify all the hashvalues are good

                if (need == 0){

                 return true;

                }

            }

        }

        //else return false.

        return false;

    }

}