Problem statement
Generate all length-n strings made from 0 and 1 that never contain 11. Return them in lexicographically increasing order. The original takeUforward prompt allows 1≤n≤20.
For n=3: [“000”, “001”, “010”, “100”, “101”]. For n=2: [“00”, “01”, “10”]. Leading zeros are required: these are fixed-length strings, not integer values.
Constraints & requirements
- CONTRACT
- Every output has exactly n characters. The substring 11 is forbidden.
Examples 3 test cases
Example 1 Case 1
- Input
n=3- Output
[000, 001, 010, 100, 101]
Zero-first order with leading zeros.
Example 2 Case 2
- Input
n=1- Output
[0, 1]
Both single characters are valid.
Example 3 Case 3
- Input
n=2- Output
[00, 01, 10]
11 must not be generated.
Hints Optional
01Find the smaller problem
What local pair could become invalid when you append one digit?
02Define the state
Zero is always safe; one is allowed only after an empty prefix or zero.
03Connect the recurrence
Explore zero first for sorted order and undo every append before its sibling branch.
How to think before coding
The entire prefix matters for output, but only its last bit controls the next choice. Append 0 unconditionally; append 1 only after an empty prefix or a trailing 0. Length n is the success condition. If using a shared builder, remove the appended bit after its child so the next sibling starts from the same prefix.
Understand the rule locally
The intuition is to reject an invalid next bit immediately, rather than finish a string and only then discover that it contains 11.
Appending 0 never creates 11. Appending 1 is allowed only when the path is empty or its last character is 0.
Why check only the last character? Earlier adjacent pairs were validated when they were created. Appending one character changes only the final pair. That is our invariant: the current prefix is already valid.
Baseline: generate everything, then filter
static List<String> filterAll(int n) {
List<String> answer = new ArrayList<>(); // Keep only completed valid strings.
for (int mask = 0; mask < (1 << n); mask++) { // Enumerate all 2^n bit patterns for n<=20.
String raw = Integer.toBinaryString(mask); // This representation drops leading zeros.
String bits = "0".repeat(n - raw.length()) + raw; // Restore exactly n positions.
if (!bits.contains("11")) answer.add(bits); // Reject invalid adjacent pairs.
}
return answer; // Increasing masks correspond to lexicographic order at a fixed length.
}Time O(n·2ⁿ), including formatting and checking. It constructs many strings we will discard. The generator below avoids those invalid branches entirely.
Backtracking solution: choose, explore, undo
Your local practice/GenerateBinaryStrings.java uses an immutable String prefix and appends 1 only when it does not end with 1. That is the same branch rule below. Here a shared StringBuilder avoids repeatedly allocating longer prefixes; it therefore needs an explicit undo, unlike your immutable-string version. The O(n) auxiliary-space analysis applies to this builder version, not all simultaneously live immutable prefixes.
public static List<String> binaryStrings(int n) {
List<String> answer = new ArrayList<>(); // Own immutable completed strings here.
buildBinary(n, new StringBuilder(), answer); // Start with an empty path.
return answer; // Zero-first exploration already gives lexicographic order.
}
private static void buildBinary(int n, StringBuilder path, List<String> answer) {
if (path.length() == n) { // A string is complete only at the requested length.
answer.add(path.toString()); // Copy the text; don't save a mutable builder reference.
return; // Do not append beyond n characters.
}
boolean canUseOne = path.length() == 0 || path.charAt(path.length() - 1) != '1'; // Avoid 11.
path.append('0'); // Zero is always safe and comes first lexicographically.
buildBinary(n, path, answer); // Finish every string with this prefix before its sibling.
path.deleteCharAt(path.length() - 1); // Restore the parent prefix after the zero branch.
if (canUseOne) { // This check refers to the original parent prefix, not the temporary zero.
path.append('1'); // Choose one only when it cannot create consecutive ones.
buildBinary(n, path, answer); // Explore this legal second branch.
path.deleteCharAt(path.length() - 1); // Undo one so the caller sees its own prefix again.
}
}Why calculate canUseOne before appending zero? The test describes the parent prefix. Testing after appending zero would falsely allow a one even after a parent ending in one.
Why delete the last character? Every call shares one StringBuilder. Before exploring the next sibling, restore exactly the prefix this frame received. Completed strings are copies, so later undo operations cannot change saved answers.
Why zero first? For equal-length binary strings, every string beginning with a given prefix plus 0 sorts before the corresponding prefix plus 1. Depth-first zero-first exploration therefore needs no final sort.
Recursion tree: n=2
"" (empty prefix) ├─ 0 │ ├─ 00 → save │ └─ 01 → save └─ 1 ├─ 10 → save └─ 11 → blocked; NO CALL
The blocked branch explains a rejected choice; it is not an executing stack frame. Draw a child only after the Java condition permits the recursive call.
Dry run and the LIFO stack

Read the text transcript
| Current prefix | Event | State after event |
|---|---|---|
| “” | Choose 0 and call | “0”; parent waits |
| “0” | Choose 0 and call | “00” |
| “00” | Save and return | output [“00”] |
| “0” | Undo 0, choose 1 | “01” |
| “01” | Save and return | output [“00”,“01”] |
| “” | Undo 0, choose 1 | “1” |
| “1” | Choose 0, save 10, undo | output adds “10” |
| “1” | One is forbidden | return to empty prefix |
Undo is performed by the resumed parent. Returning alone does not undo a shared builder.
Why this is correct
We start with a valid empty prefix. A zero preserves validity; a one preserves it exactly when the preceding character is not one. We branch on every legal next character, so every valid string is generated. Different character paths produce different strings, so there are no duplicates.
Complexity and the counting follow-up
Let A(n) be the number of valid strings. A(n)=A(n−1)+A(n−2): strings ending in zero extend a valid length n−1 string; strings ending in one must finish with 01, except the length-one base case. A(0)=1 and A(1)=2, giving A(n)=F(n+2).
Generation takes O(n·A(n)) time to copy the output strings, O(n) auxiliary path/stack space, and O(n·A(n)) output space. The alphabet-choice work is also bounded by this output-sensitive cost. Do not claim O(n) for listing all strings.
If asked only for the count, Fibonacci-style DP uses O(n) time and O(1) auxiliary space; it does not generate strings. For n=0 outside the linked constraints, our recursive method returns a list containing the empty string, not an empty list.
Mistakes and tests
- Using integers drops leading zeros.
- Appending one unconditionally creates invalid 11 branches.
- Forgetting undo changes sibling prefixes.
- Saving the builder itself instead of its text corrupts earlier answers.
- n=1 → [“0”,“1”]; n=2 → [“00”,“01”,“10”]; n=3 → five strings.
- Check every output has length n, contains no 11, appears once, and is ordered.
Recognition and related practice
A forbidden local pair suggests generate valid prefixes rather than filtering all complete candidates. Compare palindrome generation, where mirrored halves eliminate a different kind of wasted work.
Company research note
Public Amazon and Microsoft experience pages mention counting variants of binary strings with restricted consecutive ones. They do not establish that this exact list-generation contract was asked. See the Amazon candidate report and Microsoft report. Their statements differ from this task; no exact-question company badge is added. Source pages were researched 3 October 2026; the Amazon page’s search-index text was available, but direct access was blocked.
Final takeaway
Keep the prefix valid, explore zero before one, and undo every append. Generating answers has a different cost from merely counting them.
Download all tested Java solutions. These methods use Java 17+; import java.util.* in a standalone program. Use the Java comments and static dry run together to follow each call, return and update.
Practice next
Next lessonPalindrome Permutation II in Java: Build Half, Then MirrorCompare a different recursive promise and how its parent resumes.