Jobs

Interviews

Discussions

Check If a String Contains All Binary Codes of Size K

Medium

Asked by:

27 views

Topics:

StringsBit Manipulation

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.

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 indices 0, 1, 3 and 2 respectively.

Example 2:

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

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 * 10⁵
s[i] is either '0' or '1'.
1 <= k <= 20

Try coding it in LeetCode

Check If a String Contains All Binary Codes of Size K

Medium

Asked by:

27 views

Topics:

StringsBit Manipulation

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.

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 indices 0, 1, 3 and 2 respectively.

Example 2:

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

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 * 10⁵
s[i] is either '0' or '1'.
1 <= k <= 20

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s` and the maximum value of `k`?
Are `k` and the length of `s` always positive integers?
If the string `s` is empty, or if `k` is greater than the length of `s`, what should the function return?
By 'binary code of size k', do you mean all possible binary strings of length exactly `k`, or up to length `k`?
Is the comparison of binary codes case-sensitive?

Brute Force Solution

Approach

We need to see if our big string contains all possible short binary codes (strings of zeros and ones) of a specific length. The brute force method simply generates every possible short binary code and checks if it exists within the bigger string. If even one code is missing, we return false.

Here's how the algorithm would work step-by-step:

First, we need to figure out all the possible short binary codes of the given length.
For instance, if the length is two, the possible codes are '00', '01', '10', and '11'.
Next, we systematically go through each of these possible codes.
For each short code, we look for it inside the big string.
If we can't find a particular short code anywhere within the big string, we immediately know the answer is 'no'.
If we manage to find all the short codes within the big string, then we know the answer is 'yes'.

Code Implementation

def check_if_string_contains_all_binary_codes_of_size_k_brute_force(string, substring_length):
    all_possible_binary_codes = set()
    number_of_possible_codes = 2 ** substring_length

    # Generate all possible binary codes of length substring_length
    for i in range(number_of_possible_codes):
        binary_code = bin(i)[2:].zfill(substring_length)
        all_possible_binary_codes.add(binary_code)

    #Check if string contains all generated binary codes
    for binary_code in all_possible_binary_codes:
        if binary_code not in string:
            # If a code is missing, return false immediately
            return False

    # If all codes were found, return true
    return True

Big(O) Analysis

Time Complexity

O(n * 2^k) – The algorithm iterates through all possible binary codes of length k. There are 2^k such codes. For each of these codes, we search for it within the input string s of length n. The search for a substring of length k within a string of length n takes O(n) time in the worst case (using naive string search). Therefore, the overall time complexity is O(n * 2^k) because we perform a potentially O(n) search for each of the 2^k binary codes.

Space Complexity

O(2^K) – The brute force approach generates all possible binary codes of length K. This requires storing up to 2^K strings. Even if the string objects are created elsewhere and only references are held, the references themselves still occupy memory proportional to the number of codes generated, which is 2^K. The input string of size N doesn't directly influence the auxiliary space used for storing the binary codes; it's solely dependent on K.

Optimal Solution

Approach

The problem asks whether a given string contains all possible binary codes of a specific length. Instead of generating all possible binary codes and checking if each exists in the string, the optimal approach efficiently checks for their presence using a set.

Here's how the algorithm would work step-by-step:

First, calculate the maximum number of possible unique binary codes given the length 'k'. This will tell us how many codes we need to find in the string.
Create a container (like a set) to keep track of the unique binary codes we've found in the string.
Slide a window of length 'k' across the given string, extracting a substring at each position.
Convert each substring into its equivalent binary code. Add it to our container. The container will automatically prevent duplicates.
After sliding the window across the entire string, check the size of the container. If the size of the container is equal to the maximum number of possible unique binary codes we calculated initially, then the string contains all binary codes of length 'k'. Otherwise, it does not.

Code Implementation

def checkIfStringContainsAllBinaryCodes(string, substring_length):
    all_codes = set()

    # Calculate max possible unique codes.
    number_of_possible_codes = 1 << substring_length

    for i in range(len(string) - substring_length + 1):
        # Extract each substring of length k.
        sub = string[i:i + substring_length]

        all_codes.add(sub)

    # Compare number of found codes to the maximum possible.
    if len(all_codes) == number_of_possible_codes:
        return True

    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string 's' of length 'n' using a sliding window of size 'k'. Extracting a substring of length 'k' at each position and converting it to a binary code takes O(k) time. However, since 'k' is considered a constant with respect to 'n', this becomes O(1). Inserting each unique binary code into a set takes amortized O(1) time. Therefore, the dominant operation is the single pass through the string, resulting in a time complexity of O(n).

Space Complexity

O(2^k) – The primary auxiliary space is used by the set which stores unique binary codes of length k found in the string. In the worst-case scenario, the string could contain all possible binary codes of length k, resulting in the set storing 2^k unique codes. Therefore, the space complexity is directly proportional to the number of possible binary codes of length k. This leads to a space complexity of O(2^k).

Edge Cases

Case	How to Handle
Null or empty string s	Return false immediately because no binary codes can be found.
k is 0	If k is zero, all binary codes of length 0 (which is the empty string) are considered present; return true.
k is larger than the string length	Return false immediately because no binary codes of length k can be found.
String 's' is shorter than required minimum length k	Return false immediately if len(s) < k, as it's impossible to contain all binary codes of length k.
k is very large	If k is large, the number of potential binary codes 2^k grows exponentially, potentially leading to performance or memory issues depending on the implementation; consider using a bitset for efficient checking.
s contains characters other than '0' and '1'	Validate input string by throwing an error or returning false if characters other than '0' and '1' are present.
All substrings of length k in s are the same.	The algorithm should correctly identify this and return false, as it does not contain all binary codes.
Integer overflow when calculating 2^k	Check if 2^k exceeds the maximum integer value and handle it (e.g., return false if it does or use a larger data type).

Null or empty string s

How to Handle:

Return false immediately because no binary codes can be found.

k is 0

How to Handle:

If k is zero, all binary codes of length 0 (which is the empty string) are considered present; return true.

k is larger than the string length

How to Handle:

Return false immediately because no binary codes of length k can be found.

String 's' is shorter than required minimum length k

How to Handle:

Return false immediately if len(s) < k, as it's impossible to contain all binary codes of length k.

k is very large

How to Handle:

If k is large, the number of potential binary codes 2^k grows exponentially, potentially leading to performance or memory issues depending on the implementation; consider using a bitset for efficient checking.

s contains characters other than '0' and '1'

How to Handle:

Validate input string by throwing an error or returning false if characters other than '0' and '1' are present.

All substrings of length k in s are the same.

How to Handle:

The algorithm should correctly identify this and return false, as it does not contain *all* binary codes.

Integer overflow when calculating 2^k

How to Handle:

Check if 2^k exceeds the maximum integer value and handle it (e.g., return false if it does or use a larger data type).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s` and the maximum value of `k`?
Are `k` and the length of `s` always positive integers?
If the string `s` is empty, or if `k` is greater than the length of `s`, what should the function return?
By 'binary code of size k', do you mean all possible binary strings of length exactly `k`, or up to length `k`?
Is the comparison of binary codes case-sensitive?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, we need to figure out all the possible short binary codes of the given length.
For instance, if the length is two, the possible codes are '00', '01', '10', and '11'.
Next, we systematically go through each of these possible codes.
For each short code, we look for it inside the big string.
If we can't find a particular short code anywhere within the big string, we immediately know the answer is 'no'.
If we manage to find all the short codes within the big string, then we know the answer is 'yes'.

Code Implementation

def check_if_string_contains_all_binary_codes_of_size_k_brute_force(string, substring_length):
    all_possible_binary_codes = set()
    number_of_possible_codes = 2 ** substring_length

    # Generate all possible binary codes of length substring_length
    for i in range(number_of_possible_codes):
        binary_code = bin(i)[2:].zfill(substring_length)
        all_possible_binary_codes.add(binary_code)

    #Check if string contains all generated binary codes
    for binary_code in all_possible_binary_codes:
        if binary_code not in string:
            # If a code is missing, return false immediately
            return False

    # If all codes were found, return true
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, calculate the maximum number of possible unique binary codes given the length 'k'. This will tell us how many codes we need to find in the string.
Create a container (like a set) to keep track of the unique binary codes we've found in the string.
Slide a window of length 'k' across the given string, extracting a substring at each position.
Convert each substring into its equivalent binary code. Add it to our container. The container will automatically prevent duplicates.
After sliding the window across the entire string, check the size of the container. If the size of the container is equal to the maximum number of possible unique binary codes we calculated initially, then the string contains all binary codes of length 'k'. Otherwise, it does not.

Code Implementation

def checkIfStringContainsAllBinaryCodes(string, substring_length):
    all_codes = set()

    # Calculate max possible unique codes.
    number_of_possible_codes = 1 << substring_length

    for i in range(len(string) - substring_length + 1):
        # Extract each substring of length k.
        sub = string[i:i + substring_length]

        all_codes.add(sub)

    # Compare number of found codes to the maximum possible.
    if len(all_codes) == number_of_possible_codes:
        return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string s	Return false immediately because no binary codes can be found.
k is 0	If k is zero, all binary codes of length 0 (which is the empty string) are considered present; return true.
k is larger than the string length	Return false immediately because no binary codes of length k can be found.
String 's' is shorter than required minimum length k	Return false immediately if len(s) < k, as it's impossible to contain all binary codes of length k.
k is very large	If k is large, the number of potential binary codes 2^k grows exponentially, potentially leading to performance or memory issues depending on the implementation; consider using a bitset for efficient checking.
s contains characters other than '0' and '1'	Validate input string by throwing an error or returning false if characters other than '0' and '1' are present.
All substrings of length k in s are the same.	The algorithm should correctly identify this and return false, as it does not contain all binary codes.
Integer overflow when calculating 2^k	Check if 2^k exceeds the maximum integer value and handle it (e.g., return false if it does or use a larger data type).

Null or empty string s

How to Handle:

Return false immediately because no binary codes can be found.

k is 0

How to Handle:

If k is zero, all binary codes of length 0 (which is the empty string) are considered present; return true.

k is larger than the string length

How to Handle:

Return false immediately because no binary codes of length k can be found.

String 's' is shorter than required minimum length k

How to Handle:

Return false immediately if len(s) < k, as it's impossible to contain all binary codes of length k.

k is very large

How to Handle:

s contains characters other than '0' and '1'

How to Handle:

Validate input string by throwing an error or returning false if characters other than '0' and '1' are present.

All substrings of length k in s are the same.

How to Handle:

The algorithm should correctly identify this and return false, as it does not contain *all* binary codes.

Integer overflow when calculating 2^k

How to Handle:

Check if 2^k exceeds the maximum integer value and handle it (e.g., return false if it does or use a larger data type).