You are given an integer N. Your task is to count the total number of binary strings of length N such that no two consecutive 1s appear in the string.
Example 1
Input: N = 2
Output: 3
Explanation: The possible binary strings of length 2 are 00, 01, 10, and 11. Since "11" contains consecutive 1s, it is not allowed. Valid strings are 00, 01, and 10.
Example 2
Input: N = 3
Output: 5
Explanation: The possible binary strings are 000, 001, 010, 011, 100, 101, 110, and 111. Removing strings with consecutive 1s leaves 000, 001, 010, 100, and 101.
Example 3
Input: N = 1
Output: 2
Explanation: The valid strings are 0 and 1.
Sign in to write, run, and submit your solution against the full test suite.