☕ DSA Java Articles

Topics › Recursion and Backtracking › Subsequences Pattern

Generate Binary Strings Without Consecutive 1s

Medium TUF ID 493 A2Z

Java source ↗ Edit this article ↗

Problem

Given an integer n, generate every binary string of length n that does not contain two consecutive 1s, in lexicographic order (which for fixed-length binary strings is the same as increasing numeric order).

Constraints: 1 ≤ n ≤ 20. The number of valid strings is a Fibonacci number, F(n + 2), which for n = 20 is 17711, so the output itself is small even though the search space 2^n is about a million.

Example 1

n = 3
answer = ["000", "001", "010", "100", "101"]      // "011", "110", "111" contain "11"

Example 2

n = 2
answer = ["00", "01", "10"]                      // only "11" is excluded

This is the first problem in the sheet’s “subsequences pattern” section: build an answer one position at a time, and at each position make a small set of choices. The twist here is that the legal choices at a position depend on the previous choice, which is what makes pruning possible.

Approach 1: Brute force

Intuition. There are only 2^n binary strings of length n. Generate all of them by counting from 0 to 2^n - 1, write each number in binary with n digits, and keep the strings that have no "11" substring. Counting upward yields the strings in lexicographic order for free.

Algorithm.

  1. For mask = 0 .. 2^n - 1:
  2. Build the n-character string whose i-th character from the left is bit n - 1 - i of mask.
  3. If the string does not contain "11", add it to the result.
static List<String> bruteForce(int n) {
    List<String> result = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {       // counting upward is lexicographic order for fixed-width strings
        StringBuilder sb = new StringBuilder();
        for (int bit = n - 1; bit >= 0; bit--) sb.append((mask >> bit) & 1);
        String s = sb.toString();
        if (!s.contains("11")) result.add(s);
    }
    return result;
}

Complexity. Time O(2^n · n): every one of the 2^n strings is built and scanned. Space O(n) besides the output.

For n = 20 that is about twenty million character operations, which is fine, but the work is dominated by strings we throw away: fewer than 2 percent of the 2^20 candidates survive. The recursive approach avoids ever constructing an invalid prefix.

Approach 2: Optimal, recursion with pruning

Intuition. Fill the string from left to right. At position pos, placing a 0 is always legal. Placing a 1 is legal only if the previous character was not a 1. If we recurse on both legal choices and never on the illegal one, every leaf of the recursion tree is a valid string: no filtering is needed, and no work is spent on dead ends. Trying 0 before 1 produces the output in lexicographic order.

The information the next call needs is just “was the last character a 1?”, which travels as a boolean parameter.

Algorithm.

  1. build(current, pos, lastWasOne): if pos == n, record current and return.
  2. Set current[pos] = '0' and recurse with lastWasOne = false.
  3. If lastWasOne is false, set current[pos] = '1' and recurse with lastWasOne = true.
static List<String> optimal(int n) {
    List<String> result = new ArrayList<>();
    build(new char[n], 0, false, result);
    return result;
}

static void build(char[] current, int pos, boolean lastWasOne, List<String> result) {
    if (pos == current.length) {                         // base case: every position is filled
        result.add(new String(current));
        return;
    }
    current[pos] = '0';                                  // choice 1: a 0 is always legal, and sorts first
    build(current, pos + 1, false, result);
    if (!lastWasOne) {                                   // choice 2: a 1, only when the previous character was not 1
        current[pos] = '1';
        build(current, pos + 1, true, result);
    }
}

Dry run for n = 3, as the recursion tree (each node is the prefix built so far; a node has one child if it ends in 1, two otherwise):

""
├── "0"
│   ├── "00"
│   │   ├── "000"  ✓
│   │   └── "001"  ✓
│   └── "01"
│       └── "010"  ✓
└── "1"
    └── "10"
        ├── "100"  ✓
        └── "101"  ✓

Reading the leaves left to right gives 000, 001, 010, 100, 101, already sorted.

Complexity. Time O(F(n + 2) · n): the tree has exactly one leaf per valid string, every internal node has at least one child, and recording a leaf costs O(n). The output alone has F(n + 2) · n characters, so this is as good as any generator can be. Space O(n) for the recursion depth and the shared buffer.

Because the buffer is a char[] that is overwritten at current[pos] before every recursive call, there is no “undo” step; a position is always written before it is read. With a StringBuilder you would append before recursing and delete the last character afterwards.

Approach 3: Counting without generating

Intuition. Sometimes only the number of valid strings is wanted, and generating F(n + 2) strings to count them is wasteful. Classify valid strings of length len by their last character. A string ending in 0 can be extended by either 0 or 1; a string ending in 1 can only be extended by 0. So

endsWith0(len + 1) = endsWith0(len) + endsWith1(len)
endsWith1(len + 1) = endsWith0(len)

with endsWith0(1) = endsWith1(1) = 1. The total follows the Fibonacci recurrence and equals F(n + 2).

static long countOnly(int n) {
    if (n == 0) return 1;                                // the empty string
    long endsWith0 = 1, endsWith1 = 1;                   // the strings "0" and "1"
    for (int len = 2; len <= n; len++) {
        long nextEndsWith0 = endsWith0 + endsWith1;      // a 0 may follow anything
        long nextEndsWith1 = endsWith0;                  // a 1 may only follow a 0
        endsWith0 = nextEndsWith0;
        endsWith1 = nextEndsWith1;
    }
    return endsWith0 + endsWith1;
}

Complexity. Time O(n), space O(1).

This is also the proof of the time bound in Approach 2, and the test suite uses it as a cross-check: for every n up to 16 the two generators must produce identical lists whose size equals countOnly(n).

Edge cases and pitfalls