# Count N-length Binary Strings consisting of “11” as substring

Given a positive integer **N**, the task is to find the number of binary strings of length **N** which contains **“11”** as a substring.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:N = 2Output:1Explanation:The only string of length 2 that has “11” as a substring is “11”.

Input:N = 12Output:3719

**Approach:** The idea is to derive the number of possibilities of having **“11”** as a substring for binary representations starting with **0** or **1** based on the following observations:

- If the first bit is
**0**, then the starting bit does not contribute to the string having**“11”**as a substring. Therefore, the remaining**(N – 1) bits**have to form a string having**“11**” as a substring. - If the first bit is
**1**and the following bit is also**1**, then there exists**2**strings having^{(N – 2)}**“11”**as a substring. - If the first bit is
**1**but the following bit is**0**, then a string having**“11”**as a substring can be formed with remaining**(N – 2) bits**. - Therefore, the recurrence relation to generate all the binary strings of length
**N**is:

dp[i] = dp[i – 1] + dp[i – 2] + 2

^{(i – 2)}

where,

dp[i] is the string of length i having “11” as a substring.

and dp[0] = dp[1] = 0.

Follow the steps below to solve the problem:

- Initialize an array, say
**dp[]**, of size**(N + 1)**and assign**dp[0]**as**0**and**dp[1]**as**0**. - Precompute the first
**N**powers of**2**and store it in an array, say**power[]**. - Iterate over the range
**[2, N]**and update**dp[i]**as**(dp[i – 1] + dp[i – 2] + power[i – 2])**. - After completing the above steps, print the value of
**dp[N]**as the result.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to count binary strings` `// of length N having substring "11"` `void` `binaryStrings(` `int` `N)` `{` ` ` `// Initialize dp[] of size N + 1` ` ` `int` `dp[N + 1];` ` ` `// Base Cases` ` ` `dp[0] = 0;` ` ` `dp[1] = 0;` ` ` `// Iterate over the range [2, N]` ` ` `for` `(` `int` `i = 2; i <= N; i++) {` ` ` `dp[i] = dp[i - 1]` ` ` `+ dp[i - 2] ` ` ` `+ (1<<(i-2)); ` `// 1<<(i-2) means power of 2^(i-2)` ` ` `}` ` ` `// Print total count of substrings` ` ` `cout << dp[N];` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 12;` ` ` `binaryStrings(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG{` `// Function to count binary strings` `// of length N having substring "11"` `static` `void` `binaryStrings(` `int` `N)` `{` ` ` ` ` `// Initialize dp[] of size N + 1` ` ` `int` `[] dp = ` `new` `int` `[N + ` `1` `];` ` ` `// Base Cases` ` ` `dp[` `0` `] = ` `0` `;` ` ` `dp[` `1` `] = ` `0` `;` ` ` `// Stores the first N powers of 2` ` ` `int` `[] power = ` `new` `int` `[N + ` `1` `];` ` ` `power[` `0` `] = ` `1` `;` ` ` `// Generate` ` ` `for` `(` `int` `i = ` `1` `; i <= N; i++)` ` ` `{` ` ` `power[i] = ` `2` `* power[i - ` `1` `];` ` ` `}` ` ` `// Iterate over the range [2, N]` ` ` `for` `(` `int` `i = ` `2` `; i <= N; i++)` ` ` `{` ` ` `dp[i] = dp[i - ` `1` `] + dp[i - ` `2` `] + power[i - ` `2` `];` ` ` `}` ` ` ` ` `// Print total count of substrings` ` ` `System.out.println(dp[N]);` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `N = ` `12` `;` ` ` ` ` `binaryStrings(N);` `}` `}` `// This code is contributed by ukasp` |

## Python3

`# Python3 program for the above approach` `# Function to count binary strings` `# of length N having substring "11"` `def` `binaryStrings(N):` ` ` ` ` `# Initialize dp[] of size N + 1` ` ` `dp ` `=` `[` `0` `]` `*` `(N ` `+` `1` `)` ` ` `# Base Cases` ` ` `dp[` `0` `] ` `=` `0` ` ` `dp[` `1` `] ` `=` `0` ` ` `# Stores the first N powers of 2` ` ` `power ` `=` `[` `0` `]` `*` `(N ` `+` `1` `)` ` ` `power[` `0` `] ` `=` `1` ` ` `# Generate` ` ` `for` `i ` `in` `range` `(` `1` `, N ` `+` `1` `):` ` ` `power[i] ` `=` `2` `*` `power[i ` `-` `1` `]` ` ` `# Iterate over the range [2, N]` ` ` `for` `i ` `in` `range` `(` `2` `, N ` `+` `1` `):` ` ` `dp[i] ` `=` `dp[i ` `-` `1` `] ` `+` `dp[i ` `-` `2` `] ` `+` `power[i ` `-` `2` `]` ` ` `# Prtotal count of substrings` ` ` `print` `(dp[N])` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `N ` `=` `12` ` ` `binaryStrings(N)` ` ` `# This code is contributed by mohit kumar 29.` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG` `{` ` ` `// Function to count binary strings` ` ` `// of length N having substring "11"` ` ` `static` `void` `binaryStrings(` `int` `N)` ` ` `{` ` ` `// Initialize dp[] of size N + 1` ` ` `int` `[]dp = ` `new` `int` `[N + 1];` ` ` `// Base Cases` ` ` `dp[0] = 0;` ` ` `dp[1] = 0;` ` ` `// Stores the first N powers of 2` ` ` `int` `[]power = ` `new` `int` `[N + 1];` ` ` `power[0] = 1;` ` ` `// Generate` ` ` `for` `(` `int` `i = 1; i <= N; i++) {` ` ` `power[i] = 2 * power[i - 1];` ` ` `}` ` ` `// Iterate over the range [2, N]` ` ` `for` `(` `int` `i = 2; i <= N; i++) {` ` ` `dp[i] = dp[i - 1]` ` ` `+ dp[i - 2]` ` ` `+ power[i - 2];` ` ` `}` ` ` `// Print total count of substrings` ` ` `Console.WriteLine(dp[N]);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `int` `N = 12;` ` ` `binaryStrings(N);` ` ` `}` `}` `// This code is contributed by bgangwar59.` |

## Javascript

`<script>` `// JavaScript program for the above approach` ` ` `// Function to count binary strings` ` ` `// of length N having substring "11"` ` ` `function` `binaryStrings(N) {` ` ` `// Initialize dp of size N + 1` ` ` `var` `dp = Array(N + 1).fill(0);` ` ` `// Base Cases` ` ` `dp[0] = 0;` ` ` `dp[1] = 0;` ` ` `// Stores the first N powers of 2` ` ` `var` `power = Array(N+1).fill(0);` ` ` `power[0] = 1;` ` ` `// Generate` ` ` `for` `(i = 1; i <= N; i++) {` ` ` `power[i] = 2 * power[i - 1];` ` ` `}` ` ` `// Iterate over the range [2, N]` ` ` `for` `(i = 2; i <= N; i++) {` ` ` `dp[i] = dp[i - 1] + dp[i - 2] + power[i - 2];` ` ` `}` ` ` `// Print total count of substrings` ` ` `document.write(dp[N]);` ` ` `}` ` ` `// Driver Code` ` ` ` ` `var` `N = 12;` ` ` `binaryStrings(N);` `// This code contributed by aashish1995` `</script>` |

**Output**

3719

**Time Complexity:** O(N)**Auxiliary Space:** O(N)