Generate Binary Strings Without Adjacent Zeros

medium string backtracking recursion

Problem

Given a positive integer n, a binary string x is valid if every length-2 substring contains at least one "1" — equivalently, no two "0"s are adjacent. Return all valid strings of length n, in any order.

Inputn = 3

Output["010","011","101","110","111"]

Every one of these has no "00" pair. Strings like "001" or "100" are excluded.

n (1 ≤ n ≤ 12 here)

def validStrings(n):
    res = []
    cur = []

    def backtrack(i):
        if i == n:                       # built a full-length string
            res.append("".join(cur))
            return
        cur.append("1")                  # '1' is always allowed
        backtrack(i + 1)
        cur.pop()
        if i == 0 or cur[-1] == "1":     # '0' only if no adjacent zero
            cur.append("0")
            backtrack(i + 1)
            cur.pop()

    backtrack(0)
    return res

function validStrings(n) {
  const res = [];
  const cur = [];

  function backtrack(i) {
    if (i === n) {                       // built a full-length string
      res.push(cur.join(""));
      return;
    }
    cur.push("1");                       // '1' is always allowed
    backtrack(i + 1);
    cur.pop();
    if (i === 0 || cur[cur.length - 1] === "1") { // '0' needs prev '1'
      cur.push("0");
      backtrack(i + 1);
      cur.pop();
    }
  }

  backtrack(0);
  return res;
}

List<String> validStrings(int n) {
    List<String> res = new ArrayList<>();
    StringBuilder cur = new StringBuilder();
    backtrack(0, n, cur, res);
    return res;
}

void backtrack(int i, int n, StringBuilder cur, List<String> res) {
    if (i == n) {                        // built a full-length string
        res.add(cur.toString());
        return;
    }
    cur.append('1');                     // '1' is always allowed
    backtrack(i + 1, n, cur, res);
    cur.deleteCharAt(cur.length() - 1);
    if (i == 0 || cur.charAt(cur.length() - 1) == '1') { // '0' needs prev '1'
        cur.append('0');
        backtrack(i + 1, n, cur, res);
        cur.deleteCharAt(cur.length() - 1);
    }
}

void backtrack(int i, int n, string& cur, vector<string>& res) {
    if (i == n) {                        // built a full-length string
        res.push_back(cur);
        return;
    }
    cur.push_back('1');                  // '1' is always allowed
    backtrack(i + 1, n, cur, res);
    cur.pop_back();
    if (i == 0 || cur.back() == '1') {   // '0' needs prev '1'
        cur.push_back('0');
        backtrack(i + 1, n, cur, res);
        cur.pop_back();
    }
}

vector<string> validStrings(int n) {
    vector<string> res;
    string cur;
    backtrack(0, n, cur, res);
    return res;
}

Explanation

The rule “every length-2 substring has at least one 1” is just a wordy way of saying no two zeros may sit next to each other. So while building a string left to right, the only constraint is local: a 0 can never follow another 0.

That makes this a clean backtracking problem. We grow a partial string cur one character at a time using an index i (how many characters are placed so far). When i == n the string is complete, so we record a copy and return.

At each position we try the choices in order. A 1 is always safe, so we append it, recurse, then remove it (that removal is the “backtrack” that lets us try the other branch). A 0 is only safe when it would not create 00 — that holds at the very first position (i == 0) or when the previous placed character is a 1.

Because every leaf of this decision tree is a complete valid string, we never generate an invalid candidate and never need to filter afterward. The count of valid strings of length n follows the Fibonacci sequence, which is why the work stays manageable up to n = 18.

Example: for n = 3 the tree yields "010", "011", "101", "110", "111" — exactly the strings with no adjacent zeros.

Time: O(n · F(n)) Space: O(n) recursion + output