Valid Binary Strings With Cost Limit - Solution & Explanation

Problem Overview: You need to count or generate binary strings that remain valid while the accumulated cost does not exceed a given limit. Each position you append (0 or 1) affects the running cost based on the problem rule, so the goal is to explore combinations while ensuring the total cost stays ≤ k.

Approach 1: Brute Force Enumeration (Exponential Time)

Generate every binary string of length n using recursion or bitmask enumeration. For each generated string, compute its cost by iterating through characters and applying the cost rule (often based on transitions or adjacent characters). If the total cost is ≤ k, count it as valid. This approach runs in O(2^n · n) time because all possible strings are explored and each requires a linear scan to compute cost. Space complexity is O(n) for recursion depth or temporary string storage.

Approach 2: Dynamic Programming by Position and Cost (O(n · k))

A more efficient approach uses dynamic programming. Define a state like dp[i][c][b], meaning the number of ways to build a prefix of length i with cost c where the last bit is b. For each step, append either 0 or 1, compute the incremental cost based on the previous bit, and update the next state if the total remains ≤ k. This avoids recomputing prefixes repeatedly. Time complexity becomes O(n · k) since each position iterates over possible cost values, and space complexity is O(n · k) (or O(k) with rolling arrays).

Approach 3: Space-Optimized DP (O(n · k) time, O(k) space)

The DP transition only depends on the previous position. Replace the full table with two arrays that track counts for the previous step and the current step. Maintain separate counts for strings ending in 0 and 1. Each iteration updates cost buckets based on whether the appended bit increases the cost. This reduces memory while preserving the same O(n · k) time complexity. This technique is common in state compression and DP optimization.

Recommended for interviews: Start by describing the brute force generation to show you understand the search space. Then transition to the dynamic programming formulation where the state tracks prefix length, last bit, and accumulated cost. Interviewers typically expect the optimized DP solution with O(n · k) time and reduced O(k) space.