Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1’s. Output your answer modulo 10^9 + 7.
Example 1:
Input:
N = 3
Output: 5
Explanation: 5 strings are (000,
001, 010, 100, 101).
Example 2:
Input:
N = 2
Output: 3
Explanation: 3 strings are
(00,01,10).
Your Task:
Complete the function countStrings() which takes single integer n, as input parameters and returns an integer denoting the answer. You don't to print answer or take inputs. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3
class Solution:

	def countStrings(self,n):
    	# code here

Solutions:
class Solution:

	def countStrings(self, n):
		mod = 10 ** 9 + 7
		l = [0 for i in range(n + 1)]
		l[0] = 1
		l[1] = 2
		for i in range(2, n + 1):
			l[i] = l[i - 1] + l[i - 2]
		return l[-1] % mod


class Solution:

	def countStrings(self, n):
		a = 0
		b = 1
		c = 1
		for i in range(1, n + 2):
			c = (a + b) % 1000000007
			a = b
			b = c
		return c % 1000000007


class Solution:

	def countStrings(self, n):
		z = 0
		x = [0] * (n + 1)
		y = [0] * (n + 1)
		x[0] = 0
		y[0] = 0
		x[1] = 1
		y[1] = 1
		for i in range(2, n + 1):
			x[i] = (x[i - 1] + y[i - 1]) % 1000000007
			y[i] = x[i - 1] % 1000000007
		z = (x[n] + y[n]) % 1000000007
		return z


class Solution:

	def countStrings(self, n):
		e0 = [0] * (n + 1)
		e1 = [0] * (n + 1)
		e0[0] = 0
		e1[0] = 0
		e0[1] = 1
		e1[1] = 1
		for i in range(2, n + 1):
			e0[i] = e0[i - 1] + e1[i - 1] % 1000000007
			e1[i] = e0[i - 1] % 1000000007
		result = (e0[n] + e1[n]) % 1000000007
		return result


class Solution:

	def countStrings(self, n):
		ENDZ = [0] * (n + 1)
		ENDO = [0] * (n + 1)
		ENDZ[0] = 0
		ENDO[0] = 0
		ENDZ[1] = 1
		ENDO[1] = 1
		for i in range(2, n + 1):
			ENDZ[i] = (ENDZ[i - 1] + ENDO[i - 1]) % 1000000007
			ENDO[i] = ENDZ[i - 1] % 1000000007
		result = (ENDZ[n] + ENDO[n]) % 1000000007
		return result


class Solution:

	def countStrings(self, n):
		EZ = [0] * (n + 1)
		E0 = [0] * (n + 1)
		EZ[0] = 0
		EZ[1] = 1
		E0[0] = 0
		E0[1] = 1
		for i in range(2, n + 1):
			EZ[i] = (EZ[i - 1] + E0[i - 1]) % 1000000007
			E0[i] = EZ[i - 1] % 1000000007
		res = (EZ[n] + E0[n]) % 1000000007
		return res


class Solution:

	def countStrings(self, n):
		z = [0] * (n + 1)
		o = [0] * (n + 1)
		z[0] = 0
		z[1] = 1
		o[0] = 0
		o[1] = 1
		for i in range(2, n + 1):
			z[i] = (z[i - 1] + o[i - 1]) % (10 ** 9 + 7)
			o[i] = z[i - 1] % (10 ** 9 + 7)
		a = (z[-1] + o[-1]) % (10 ** 9 + 7)
		return a


class Solution:

	def countStrings(self, n):
		if n == 0:
			return 0
		elif n == 1:
			return 2
		elif n == 2:
			return 3
		else:
			l = [0, 2, 3]
			while len(l) != n + 1:
				l.append(l[-1] + l[-2])
			return l[-1] % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n):
		z = [0] * (n + 1)
		o = [0] * (n + 1)
		z[0] = 0
		z[1] = 1
		o[0] = 0
		o[1] = 1
		for i in range(2, n + 1):
			z[i] = (z[i - 1] + o[i - 1]) % 1000000007
			o[i] = z[i - 1] % 1000000007
		a = (z[-1] + o[-1]) % 1000000007
		return a


import numpy as np

class Solution:

	def rec_sol(self, n, isone):
		if n == 0:
			return 1
		if isone:
			return self.rec_sol(n - 1, False)
		else:
			return self.rec_sol(n - 1, True) + self.rec_sol(n - 1, False)

	def mem_sol(self, n, isone, dp):
		if n == 0:
			return 1
		if dp[n][isone] != -1:
			return dp[n][isone]
		if isone == 1:
			dp[n][isone] = self.mem_sol(n - 1, 0, dp)
			return dp[n][isone]
		else:
			dp[n][isone] = (self.mem_sol(n - 1, 1, dp) % 1000000007 + self.mem_sol(n - 1, 0, dp) % 1000000007) % 1000000007
			return dp[n][isone]

	def dp_sol(self, n):
		dp = np.array([[0] * 2] * (n + 1))
		c = 1000000007
		dp[1][0] = 1
		dp[1][1] = 1
		for i in range(2, n + 1):
			dp[i][0] = (dp[i - 1][0] % c + dp[i - 1][1] % c) % c
			dp[i][1] = dp[i - 1][0]
		return (dp[n][0] % c + dp[n][1] % c) % c

	def countStrings(self, n):
		return self.dp_sol(n)


class Solution:

	def countStrings(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 2
		eo = [0] * n
		ea = [0] * n
		ea[1] = 1
		eo[1] = 1
		for i in range(2, n):
			eo[i] = eo[i - 1] + ea[i - 1]
			ea[i] = eo[i - 1]
		eo.append(eo[-1] + ea[-1])
		ea.append(eo[-2])
		return (eo[-1] + ea[-1]) % 1000000007


class Solution:

	def countStrings(self, n):
		if n < 3:
			return n + 1
		l = [0] * (n + 1)
		l[0] = 1
		l[1] = 2
		l[2] = 3
		for i in range(3, n + 1):
			l[i] = (l[i - 1] + l[i - 2]) % 1000000007
		return l[n]


class Solution:

	def countStrings(self, n):
		dp0 = [0, 1]
		dp1 = [0, 1]
		for i in range(2, n + 1):
			dp0.append(dp1[i - 1])
			dp1.append((dp0[i - 1] + dp1[i - 1]) % 1000000007)
		return (dp0[n] + dp1[n]) % 1000000007


class Solution:

	def countStrings(self, n):
		dp = [0 for i in range(n + 1)]
		z = 1
		o = 0
		m = 10 ** 9 + 7
		res = 0
		for i in range(1, n):
			(z, o) = ((o + z) % m, z)
		res = (2 * z + o) % m
		return res


class Solution:

	def countStrings(self, n):
		if n <= 2:
			return n + 1
		a = 2
		b = 3
		for i in range(3, n + 1):
			c = (a + b) % (10 ** 9 + 7)
			a = b
			b = c
		return c


import sys
sys.setrecursionlimit(10000000)

class Solution:
	cache = dict()

	def countStrings(self, n):
		if n == 0:
			return 1
		if n == 1:
			return 2
		if self.cache.get(n):
			return self.cache.get(n)
		value = self.countStrings(n - 2) + self.countStrings(n - 1)
		value = value % (10 ** 9 + 7)
		if self.cache.get(n) is None:
			self.cache[n] = value
		return value


class Solution:

	def countStrings(self, n):
		zero = 1
		one = 1
		mod = 10 ** 9 + 7
		ans = zero + one
		if n == 1:
			return ans
		i = 2
		while i <= n:
			one = zero % mod
			zero = ans % mod
			ans = (one + zero) % mod
			i += 1
		return ans


class Solution:

	def countStrings(self, n):
		oc1 = 1
		oc0 = 1
		for i in range(2, n + 1):
			nc1 = oc0
			nc0 = oc0 + oc1
			oc0 = nc0
			oc1 = nc1
		return (oc0 + oc1) % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n):
		a = [0 for i in range(n)]
		b = [0 for i in range(n)]
		mod = 10 ** 9 + 7
		a[0] = 1
		b[0] = 1
		for i in range(1, n):
			a[i] = (a[i - 1] + b[i - 1]) % mod
			b[i] = a[i - 1] % mod
		return (a[n - 1] + b[n - 1]) % mod


class Solution:

	def countStrings(self, n):
		mod = 10 ** 9 + 7
		l1 = [0 for i in range(n)]
		l2 = [0 for i in range(n)]
		l1[0] = 1
		l2[0] = 1
		for i in range(1, n):
			l1[i] = l1[i - 1] + l2[i - 1]
			l2[i] = l1[i - 1]
		return (l1[-1] + l2[-1]) % mod


mod = 10 ** 9 + 7

def multiply(mat1, mat2):
	ans = [[0 for i in range(2)] for j in range(2)]
	for i in range(2):
		for j in range(2):
			for k in range(2):
				ans[i][j] += mat1[i][k] * mat2[k][j] % mod
	return ans

def func(mat, n):
	if n == 1:
		return mat
	temp = func(mat, n // 2)
	if n % 2 == 0:
		return multiply(temp, temp)
	return multiply(multiply(temp, temp), mat)

class Solution:

	def countStrings(self, N):
		mat = [[1, 1], [1, 0]]
		ans = func(mat, N + 2)
		return ans[0][1] % mod


class Solution:

	def countStrings(self, n):
		MOD = 10 ** 9 + 7
		dp = [0] * n
		dp2 = [0] * n
		dp[0] = 1
		dp2[0] = 1
		for i in range(1, n):
			dp[i] = (dp[i - 1] + dp2[i - 1]) % MOD
			dp2[i] = dp[i - 1] % MOD
		return (dp[n - 1] + dp2[n - 1]) % MOD


class Solution:

	def countStrings(self, N):
		mod = 10 ** 9 + 7
		z = 1
		o = 1
		s = z + o
		if N == 1:
			return s
		i = 2
		while i <= n:
			o = z % mod
			z = s % mod
			s = (z + o) % mod
			i += 1
		return s


class Solution:

	def countStrings(self, n):
		dp = [-1] * n
		if n == 1:
			return 2
		dp[0] = 2
		dp[1] = 3
		i = 2
		while i < n:
			dp[i] = (dp[i - 2] + dp[i - 1]) % 1000000007
			i += 1
		return dp[n - 1]


class Solution:

	def countStrings(self, n):
		dp = [0 for i in range(n + 1)]
		dp[0] = 2
		dp[1] = 3
		i = 2
		while i < n:
			dp[i] = (dp[i - 2] + dp[i - 1]) % 1000000007
			i += 1
		return dp[n - 1]


mod = 10 ** 9 + 7

class Solution:

	def countStrings(self, n):
		sub_str_ending_zero = 1
		sub_str_ending_one = 1
		for i in range(1, n):
			tmp = (sub_str_ending_zero + sub_str_ending_one) % mod
			sub_str_ending_one = sub_str_ending_zero
			sub_str_ending_zero = tmp
		return (sub_str_ending_zero + sub_str_ending_one) % mod


class Solution:

	def countStrings(self, n):
		a = 1
		b = 1
		i = 1
		while i < n:
			temp = a + b
			a = b
			b = temp
			i += 1
		return (a + b) % 1000000007


class Solution:

	def countStrings(self, n):
		if n == 1:
			return 2
		if n == 2:
			return 3
		dp = [-1] * n
		dp[0] = 2
		dp[1] = 3
		for i in range(2, n):
			dp[i] = dp[i - 2] + dp[i - 1]
		return dp[n - 1] % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n):
		dp = {}
		mod = 10 ** 9 + 7
		dp = [{} for _ in range(n)]
		dp[-1][0] = 1
		dp[-1][1] = 1
		for i in range(n - 2, -1, -1):
			for prev in dp[i + 1]:
				if prev == 0:
					dp[i][0] = dp[i + 1][0]
					dp[i][1] = dp[i + 1][0]
				else:
					dp[i][0] += dp[i + 1][1]
		total = 0
		total += dp[0][0]
		total += dp[0][1]
		return total % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n):
		out = [2, 3]
		for i in range(n - 2):
			out.append(out[-1] + out[-2])
		return out[n - 1] % 1000000007


class Solution:

	def countStrings(self, n):
		dp0 = 1
		dp1 = 1
		for i in range(2, n + 1):
			(dp0, dp1) = (dp1, dp0 + dp1)
		return (dp0 + dp1) % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n):
		a = 1
		b = 1
		i = 1
		while i < n:
			tmp = a + b
			a = b
			b = tmp
			i += 1
		return (a + b) % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n):
		dp = [[0 for _ in range(n + 1)] for _ in range(2)]
		dp[0][1] = 1
		dp[1][1] = 1
		for i in range(2, len(dp[0])):
			dp[1][i] = dp[0][i - 1]
			dp[0][i] = dp[0][i - 1] + dp[1][i - 1]
		return (dp[0][-1] + dp[1][-1]) % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n):
		countB = 1
		countS = 1
		for _ in range(2, n + 1):
			prev_countB = countB
			prev_countS = countS
			countS = prev_countB + prev_countS
			countB = prev_countS
		result = countS + countB
		return result % 1000000007


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def countStrings(self, n):
		g = {}

		def recr(val, index):
			if (val, index) in g:
				return g[val, index]
			if index == n:
				return 1
			if val == '':
				ans = recr(0, index + 1) + recr(1, index + 1)
			elif val == 0:
				ans = recr(1, index + 1) + recr(0, index + 1)
			elif val == 1:
				ans = recr(0, index + 1)
			g[val, index] = ans
			return ans
		return recr('', 0) % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n):
		a = []
		b = []
		a.append(1)
		b.append(1)
		for i in range(1, n):
			temp1 = a[i - 1] + b[i - 1]
			a.append(temp1)
			temp2 = a[i - 1]
			b.append(temp2)
		return (a[n - 1] + b[n - 1]) % 1000000007


import math

class Solution:

	def countStrings(self, n):
		if n == 1:
			return 2
		first = 2
		sec = 3
		for i in range(2, n + 1):
			k = sec
			sec = sec + first
			first = k
		return first % (1000000000 + 7)


class Solution:

	def countStrings(self, n):
		dp = [[0] * 2 for i in range(n)]
		dp[0][0] = 1
		dp[0][1] = 1
		for i in range(1, n):
			dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % 1000000007
			dp[i][1] = dp[i - 1][0]
		return sum(dp[n - 1]) % 1000000007


class Solution:

	def countStrings(self, n):
		dp = [0] * (n + 1)
		dp1 = [1] * (n + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = dp[i - 1] + dp1[i - 1]
			dp1[i] = dp[i - 1]
		s = dp[-1] + dp1[-1]
		return s % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n):
		endl = [0] * (n + 1)
		endz = [0] * (n + 1)
		endl[0] = endz[0] = 0
		endl[1] = endz[1] = 1
		for i in range(2, n + 1):
			endl[i] = endz[i - 1]
			endz[i] = endl[i - 1] + endz[i - 1]
		return (endl[-1] + endz[-1]) % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n):
		zeros = 1
		ones = 1
		for i in range(2, n + 1):
			temp = zeros
			zeros = zeros + ones
			ones = temp
			zeros = zeros % 1000000007
			ones = ones % 1000000007
		return (ones + zeros) % 1000000007


class Solution:

	def countStrings(self, n):
		end_with_zero = [0] * (n + 1)
		end_with_one = [0] * (n + 1)
		end_with_zero[1] = 1
		end_with_one[1] = 1
		for i in range(2, n + 1):
			end_with_zero[i] = end_with_zero[i - 1] + end_with_one[i - 1]
			end_with_one[i] = end_with_zero[i - 1]
		return (end_with_zero[-1] + end_with_one[-1]) % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n):
		if n == 0:
			return 0
		elif n == 1:
			return 2
		one = 1
		zero = 1
		for i in range(2, n + 1):
			temp = zero
			zero = one + zero
			one = temp
		temp = one + zero
		mod = 10 ** 9 + 7
		return temp % mod


class Solution:

	def countStrings(self, n):
		endWithZero = [0] * (n + 1)
		endWithOne = [0] * (n + 1)
		endWithZero[0] = 0
		endWithZero[1] = 1
		endWithOne[0] = 0
		endWithOne[1] = 1
		for i in range(2, n + 1):
			temp = endWithOne[i - 1]
			endWithOne[i] = endWithZero[i - 1]
			endWithZero[i] = endWithZero[i - 1] + temp
		return (endWithOne[-1] + endWithZero[-1]) % (pow(10, 9) + 7)


class Solution:

	def countStrings(self, n):
		end_1 = [0, 1]
		end_0 = [0, 1]
		if n == 0:
			return 0
		elif n == 1:
			return 2
		for i in range(2, n + 1):
			end_1.append(end_0[i - 1])
			end_0.append(end_1[i - 1] + end_0[i - 1])
		b = end_0[n] + end_1[n]
		return b % (pow(10, 9) + 7)


class Solution:

	def countStrings(self, n):
		MOD = 10 ** 9 + 7
		if n == 1:
			return 2
		if n == 2:
			return 3
		count1 = 2
		count2 = 3
		for i in range(3, n + 1):
			nextcount = (count1 + count2) % MOD
			(count1, count2) = (count2, nextcount)
		return nextcount


class Solution:

	def countStrings(self, n):
		way = [1, 1]
		for x in range(n - 1):
			(way[0], way[1]) = (way[0] + way[1], way[0])
		return sum(way) % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n):

		def countBinaryStrings(n):
			MOD = 10 ** 9 + 7
			count0 = 1
			count1 = 1
			for i in range(2, n + 1):
				new_count0 = (count0 + count1) % MOD
				new_count1 = count0
				count0 = new_count0
				count1 = new_count1
			return (count0 + count1) % MOD
		return countBinaryStrings(n)