Binary Strings Without Two Zeros in a Row

Medium

Given an integer length, return every string of length characters made of 0 and 1 in which two zeros never stand next to each other. The strings may be returned in any order.

Example 1

length=2 → ['01', '10', '11']

Of the four strings of length 2, only 00 is ruled out.

Example 2

length=4 → ['0101', '0110', '0111', '1010', '1011', '1101', '1110', '1111']

Eight strings qualify: 0101, 0110, 0111, 1010, 1011, 1101, 1110, 1111.

Constraints

1 ≤ length ≤ 18

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation String Backtracking

Similar problems

Every Shorthand of a Word Medium Every Case Spelling Medium Two Disjoint Palindromic Picks Medium Shortest Unambiguous Shorthand Hard Best Word Set From Tiles Hard

Input

length=2

Expected

['01', '10', '11']

Run checks the first 3 tests in your browser. Submit checks all 14 tests on the server, hidden ones included.