LESSON 335 OF 410 · DYNAMIC PROGRAMMING

Binary Strings of Given Length in Python: Counting with DP

Given a non-negative integer N return the number of binary strings of length N

Example:

Input: N = 3
Output: 8
Explanation: [
    "000",
    "001",
    "010",
    "011",
    "100",
    "101",
    "110",
    "111"
]

Notes: N <= 30

STEP 1 OF 5

Guided

Ctrl + Enter to check

Binary Strings Of Given Length in Python, explained

Problem overview

The method countBinaryStrings receives a non-negative integer n and returns how many binary strings of length n exist. A binary string is made only of the characters 0 and 1. The problem says n is at most 30.

For n = 3 the answer is 8, because the strings are 000, 001, 010, 011, 100, 101, 110 and 111. The task asks for the count, not the strings, so the method never has to build them.

Approach: extend shorter strings

Let dp[i] be the number of binary strings of length i. This is dynamic programming: define the answer for a size in terms of the answer for the size before it.

A string of length i is a string of length i - 1 followed by one more character. That last character is either 0 or 1, so every shorter string can be extended in exactly two ways, and different shorter strings or different last characters never produce the same result. So the count doubles at every step:

dp[i] = 2 * dp[i - 1]

The recurrence needs a starting point. For length 1 the only strings are 0 and 1, so dp[1] = 2. From there, dp[2] = 4, dp[3] = 8, and so on. Doubling a number n - 1 times starting from 2 gives 2 ** n, so the answer is the power of two. The table makes the recurrence visible, which is the point of the lesson, and the closed form is a useful way to double-check it.

Step by step

Create the table. dp = [0] * (n + 1) repeats the one-element list [0] to give n + 1 zeros. The extra slot lets index n exist, because the indices of a list of length n + 1 run from 0 to n.
Set the base case. dp[1] = 2.
Loop from 2 to n inclusive. range(2, n + 1) is needed because the end of a range is excluded. Each entry is computed after the entry before it.
Fill each entry. dp[i] = dp[i - 1] * 2.
Return dp[n].

The solution in Python

class Solution:
    def countBinaryStrings(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[1] = 2
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] * 2
        return dp[n]

Python-specific points:

Integers do not overflow. With n = 30 the result is 1073741824, and Python would keep going far beyond that. In a language with 32-bit signed integers, 2 ** 31 would no longer fit, so there the limit on n matters.
[0] * (n + 1) is safe for numbers. For nested lists, the same trick copies references, but a flat list of integers is fine.

Complexity

The loop runs n - 1 times with constant work in each, so the time is O(n). The table holds n + 1 numbers, so the space is O(n). Only the previous entry is ever read, so a single running variable would reduce the space to O(1), and 2 ** n or 1 << n gives the answer directly.

Edge cases and common mistakes

n = 1. The loop does not run, and the result is dp[1], which is 2.
n = 0. The statement allows it. There is exactly one string of length zero, the empty string, so the mathematically correct count is 1. This solution cannot handle it: dp has a single element, and dp[1] = 2 raises IndexError: list assignment index out of range. If you need to support 0, return 1 early for that case, or set dp[0] = 1 and start the loop at 1.
Range end. range(2, n) stops one step early and leaves dp[n] as 0.
Counting by listing. Generating all strings works for small n, but the count grows as 2 to the power n, so it is far too slow for n = 30, which has over a billion strings.

Testing

n = 1 returns 2.
n = 2 returns 4.
n = 3 returns 8.
n = 5 returns 32.
n = 30 returns 1073741824.

Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free