Given a binary string s and an integer k, return true if every binary code of length k is a substring of s.
Otherwise, return false.
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 indices 0, 1, 3 and 2 respectively.
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.
Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and does not exist in the array.
Constraints:
- 1 <= s.length <= 5 * 105
- s[i] is either '0' or '1'.
- 1 <= k <= 20.
Contents
- Solution 1 - Generate all possible K length substrings, store them in a HashSet, and check if it has K length binary strings
In this approach, we are going to generate all possible k length substrings and store them in a HashSet, while storing them into the set,
check if it reaches size of k length binary strings which is 2k. For example, if k is 2,
then possible binary substrings are 00, 01, 10 and 11, so total number of combinations possible with k distinct
0's and 1's are 2k.
import java.util.HashSet;
public class CheckIfStringContainsAllBinaryCodesOfSizeK {
static boolean hasAllCodes(String s, int k) {
int expectedTotal = 1 <<k; // equivalent to Math.pow(2, k)
HashSet<String> uniqueBinaryCodes = new HashSet<>();
for(int i=0; i<s.length()-(k-1); i++) {
String kLengthBinary = s.substring(i, i+k);
uniqueBinaryCodes.add(kLengthBinary);
if(uniqueBinaryCodes.size() == expectedTotal){
return true;
}
}
return false;
}
public static void main(String[] args) {
System.out.println(hasAllCodes("00110110", 2));
System.out.println(hasAllCodes("00110", 2));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n * k) time where n is the length of input string s.
Space complexity: O(n * k) , since we are storing n possible substrings and each of length k, we can also say this is 2k
as there will be these many binary substrings possible with k distinct 0's and 1's.
Above implementations source code can be found at
GitHub link for Java code