Generate Binary Strings Without Consecutive 1s
MediumTrack only the previous character
Problem
Generate all binary strings of length n that never contain two adjacent 1s.
Build the string bit by bit; only add a 1 when the previous bit was 0.
The idea
At each position append 0 freely, and append 1 only when the previous character was not a 1. Carrying just the last character is enough state, because the constraint is purely local.
The trick
- The state is a single boolean: did the previous position hold a 1?
- The count of such strings follows the Fibonacci numbers.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — n = 3 Values: 3.
1f(pos, last, cur):2 if pos==n: output cur; return3 f(pos+1, 0, cur+'0')4 if last==0: f(pos+1, 1, cur+'1')Input
- array
- [3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 2
- Output:
- ['00', '01', '10']
- Explanation:
- 00, 01, 10 — never two 1s in a row.
Example 2
- Input:
- n = 3
- Output:
- ['000', '001', '010', '100', '101']
- Explanation:
- 5 valid strings.
Example 3
- Input:
- n = 1
- Output:
- ['0', '1']
- Explanation:
- 0 and 1.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.