Binary strings without consecutive ones
Filed under Microsoft
Free read 2 of 3Check input constraints for n to determine if iterative DP or matrix exponentiation is needed.
The question
Count the number of binary strings of length n that do not contain consecutive 1s.
Constraints
- 1 <= n <= 30
- Return an integer count of valid binary strings.
Examples
- Input
- n = 2
- Output
- 3
- Why
- Valid strings are '00', '01', '10'. ('11' is invalid).
Approach
Check input constraints for n to determine if iterative DP or matrix exponentiation is needed.
Generate all binary strings of length n recursively and filter out those containing '11' (O(2^n) time).
Recognize this as a Fibonacci sequence problem. Let ending0[i] and ending1[i] be the count of valid strings of length i ending in 0 and 1 respectively. ending0[i] = ending0[i-1] + ending1[i-1], ending1[i] = ending0[i-1].
n = 1 handling correctly.
Solution
O(n) time, O(1) space
def countStrings(n: int) -> int:
if n <= 0:
return 0
end_with_0 = 1
end_with_1 = 1
for _ in range(2, n + 1):
new_end_0 = end_with_0 + end_with_1
new_end_1 = end_with_0
end_with_0, end_with_1 = new_end_0, new_end_1
return end_with_0 + end_with_1
Tips
- What they are testing: Test with n = 1 (should return 2: '0', '1') and n = 3 (should return 5: '000', '001', '010', '100', '101').
- Common mistake: Attempting to generate all 2^n strings and filter them, which results in exponential Time Limit Exceeded errors for larger n.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.