โ† Microsoft questions

Binary strings without consecutive ones

Filed under Microsoft

Free read 2 of 3

Check 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

  1. Check input constraints for n to determine if iterative DP or matrix exponentiation is needed.

Solution

O(n) time, O(1) space

Python
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.