Start learning free

LESSON 341 OF 410 · FREE CODING INTERVIEW QUESTIONS

Binary Strings with at most K Consecutive Ones in Python (Time Complexity: O(N*K))

Practice O(n * k) Read the full explanation

Given two non-negative integers N and K, return the number of binary strings of length N with at most K consecutive ones

Example:

Input: N = 4, K = 2
Output: 13
Explanation: [
    "0000",
    "0001",
    "0010",
    "0011",
    "0100",
    "0101",
    "0110",
    "1000",
    "1001",
    "1010",
    "1011",
    "1100",
    "1101",
]
"0111", "1110" and "1111" are not valid because they have more than 2 consecutive ones
Notes: K <= N <= 30
STEP 1 OF 9
    Ctrl + Enter to check

    PYTHON · FREE CODING INTERVIEW QUESTIONS

    Binary Strings With At Most K Consecutive Ones in Python, explained

    Understanding the Problem

    The core challenge of this problem is to generate all possible binary strings of length N and count those that have at most K consecutive ones. This problem is significant in various fields such as coding theory, data compression, and error detection.

    Potential pitfalls include misunderstanding the constraints and generating strings with more than K consecutive ones.

    Approach

    To solve this problem, we can use dynamic programming (DP). The idea is to build the solution incrementally and store intermediate results to avoid redundant calculations.

    We can define a DP table where dp[i][j] represents the number of valid binary strings of length i that end with exactly j consecutive ones.

    Naive Solution

    A naive solution would involve generating all possible binary strings of length N and then filtering out those with more than K consecutive ones. This approach is not optimal due to its exponential time complexity.

    Optimized Solution

    Using dynamic programming, we can achieve a more efficient solution. The DP approach involves the following steps:

    1. Initialize a DP table with dimensions (N+1) x (K+1).
    2. Set the base cases: dp[0][0] = 1 (an empty string is a valid string).
    3. Iterate through the lengths from 1 to N and update the DP table based on the previous values.
    4. Sum up the values in the last row of the DP table to get the final result.

    Algorithm

    Here is a step-by-step breakdown of the algorithm:

    1. Initialize a DP table dp with dimensions (N+1) x (K+1) and set all values to 0.
    2. Set the base case: dp[0][0] = 1.
    3. For each length i from 1 to N:
      • For each count of consecutive ones j from 0 to K:
        • If j == 0, update dp[i][0] by summing all dp[i-1][x] for x from 0 to K.
        • If j > 0, update dp[i][j] by setting it to dp[i-1][j-1].
    4. Sum up all values in the last row of the DP table to get the final result.

    Code Implementation

    def count_binary_strings(N, K):
    # Initialize the DP table
    dp = [[0] * (K + 1) for _ in range(N + 1)]
    
    # Base case: an empty string is a valid string
    dp[0][0] = 1
    
    # Fill the DP table
    for i in range(1, N + 1):
        for j in range(K + 1):
            if j == 0:
                # Sum all dp[i-1][x] for x from 0 to K
                dp[i][0] = sum(dp[i-1])
            else:
                # Set dp[i][j] to dp[i-1][j-1]
                dp[i][j] = dp[i-1][j-1]
    
    # Sum up all values in the last row to get the final result
    return sum(dp[N])

# Example usage
N = 4
K = 2
print(count_binary_strings(N, K))  # Output: 13

    Complexity Analysis

    The time complexity of this approach is O(N*K) because we iterate through the DP table of size (N+1) x (K+1). The space complexity is also O(N*K) due to the storage required for the DP table.

    Edge Cases

    Potential edge cases include:

    • N = 0: The output should be 1 (an empty string).
    • K = 0: Only strings with no consecutive ones are valid.
    • K >= N: All binary strings of length N are valid.

    Testing

    To test the solution comprehensively, consider the following test cases:

    • N = 4, K = 2: Expected output is 13.
    • N = 5, K = 1: Expected output is 8.
    • N = 3, K = 0: Expected output is 2.

    Use testing frameworks like unittest or pytest to automate the testing process.

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Break down the problem into smaller subproblems.
    • Use dynamic programming to store intermediate results and avoid redundant calculations.
    • Think about edge cases and how to handle them.
    • Practice solving similar problems to improve your problem-solving skills.

    Conclusion

    In this blog post, we discussed how to solve the problem of counting binary strings with at most K consecutive ones using dynamic programming. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free