Coding

Generate Binary Strings Without Consecutive 1s

Asked at

Google

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer n, return all binary strings of length n that do not contain consecutive 1s. Return the result in lexicographically increasing order.

A binary string is a string consisting only of characters** '0'** and** '1**'.

Input: n = 3 Output: ["000", "001", "010", "100", "101"] **Explanation: **All strings are of length 3 and do not contain consecutive 1s.

Input: n = 2 **Output: **["00", "01", "10"]

Input: n = 1

1 <= n <= 20

cpp

class Solution {
public:
    vector<string> generateBinaryStrings(int n) {
        // Your code goes here
    }
};

java

class Solution {
    public List<String> generateBinaryStrings(int n) {
        // Your code goes here
    }
}

python

class Solution:
    def generateBinaryStrings(self, n):
        # Your code goes here

javascript

class Solution {
    generateBinaryStrings(n) {
        // Your code goes here
    }
}

csharp

public class Solution
{
    public List<string> GenerateBinaryStrings(int n)
    {
        // Your code goes here
    }
}

func generateBinaryStrings(n int) []string {

Stuck? Show a way to structure it+

01Define output order and n=0 behavior
02Recurse with index and previous-bit state
03Always branch to 0, conditionally branch to 1
04Emit when the built string reaches length n

Reference answer

Start by restating the input contract for Generate Binary Strings Without Consecutive 1s and testing the smallest boundary case before choosing the algorithm. Use backtracking with the previous bit as state. At each position append 0; append 1 only when the previous bit is not 1. This produces every valid length-n string once and naturally enforces the constraint. Explain the invariant while coding, then show how each update preserves it. If F(n) is the number of valid strings, materializing them costs O(n * F(n)) time and O(n) recursion space, excluding the returned strings. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

How many such strings exist?
Tests: follow-up reasoning
How would you count rather than generate them?
Tests: follow-up reasoning

Hiring now

Google has 52 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Small Business Field Sales Representative
Denver, Colorado
Senior Technical Program Manager, Special Projects
Denver, Colorado; Lakewood, Colorado, United States
OSP Engineering Lead, Technical Operations
Denver, Colorado

Or practice this question first

Next question