Get started

Generate Binary Strings Without Adjacent Zeros — Medium Problem & Solution

A binary string is valid when every substring of length 2 contains at least one 1 — in other words, no two 0s are adjacent.

Problem statement

A binary string is valid when every substring of length 2 contains at least one 1 — in other words, no two 0s are adjacent.

Return all valid binary strings of length n, in ascending lexicographic order.

Example 1

Input: n = 3
Output: ["010","011","101","110","111"]
Explanation: `000`, `001` and `100` contain `00`.

Example 2

Input: n = 1
Output: ["0","1"]

Example 3

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

Constraints

  • 1 <= n <= 18

How to solve Generate Binary Strings Without Adjacent Zeros

Depth-first construction with a one-character look-back. Because all strings have the same length and 0 is tried before 1, the depth-first order is the lexicographic order.

Approach

  1. dfs(prefix): if prefix has length n, record it.
  2. If prefix is empty or ends with 1, recurse on prefix + "0".
  3. Always recurse on prefix + "1".

Why it works

A string has no 00 exactly when no 0 follows a 0, which is the only append the search forbids — so it produces precisely the valid strings, each once. Two strings first differ at some position where the one with 0 was explored first, so the output is sorted.

Complexity

  • Time — O(n · F(n+2)) — the count of valid strings is a Fibonacci number
  • Space — O(n) recursion depth besides the output

Pitfalls

  • The first character may be 0 (there is no previous character).
  • n = 1 gives both 0 and 1.
  • Generating all 2^n strings and filtering works but wastes most of its time.

Reference solution

Python

from typing import List

def validStrings(n: int) -> List[str]:
    out = []
    buf = []

    def dfs():
        if len(buf) == n:
            out.append(''.join(buf))
            return
        if not buf or buf[-1] == '1':
            buf.append('0')
            dfs()
            buf.pop()
        buf.append('1')
        dfs()
        buf.pop()

    dfs()
    return out

JavaScript

var validStrings = function(n) {
    var out = [];
    var buf = [];
    var dfs = function() {
        if (buf.length === n) {
            out.push(buf.join(''));
            return;
        }
        if (buf.length === 0 || buf[buf.length - 1] === '1') {
            buf.push('0');
            dfs();
            buf.pop();
        }
        buf.push('1');
        dfs();
        buf.pop();
    };
    dfs();
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 424 strings problems · the whole catalogue

Learn the technique: Strings · Bit Manipulation