Problem overview
A binary string contains only the characters 0 and 1. The method countBinaryStrings(int n) returns how many different binary strings of length n exist. It counts them; it does not build them. The limit is n <= 30.
For n = 3 the answer is 8, because the strings are 000, 001, 010, 011, 100, 101, 110 and 111.
Approach: each extra character doubles the count
Look at how the strings of one length relate to the strings of the next. Every string of length i is a string of length i - 1 followed by one more character, and that character is either 0 or 1. So each shorter string produces exactly two longer ones, and no two shorter strings produce the same longer one. In terms of counts:
count(i) = 2 * count(i - 1)
A length of 1 has only the strings 0 and 1, so count(1) = 2. From there the counts are 2, 4, 8, 16 and so on: powers of two. The count for length n is 2^n, which answers the common question of why the number of binary strings of length n is 2^n. Each of the n positions is an independent choice between two characters.
The lesson computes the answer with dynamic programming: a table dp where dp[i] stores the answer for length i, filled from the smallest length upward using the doubling rule. Here the rule is so simple that a table is more than the problem needs, but it shows the pattern used in harder problems: define what each table entry means, fill in a base case, then derive each entry from earlier ones.
Step by step
- Declare
int[] dp = new int[n + 1]. Entryiholds the count for lengthi, and the sizen + 1makesdp[n]a valid index. Java fills a newintarray with zeros. - Set the base case.
dp[1] = 2, since a single character can be0or1. - Loop
ifrom 2 toninclusive. Withi <= nthe last entry,dp[n], is filled too. - Apply the recurrence.
dp[i] = dp[i - 1] * 2doubles the previous entry. - Return
dp[n].
The solution in Java
class Solution {
public int countBinaryStrings(int n) {
int[] dp = new int[n + 1];
dp[1] = 2;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] * 2;
}
return dp[n];
}
}
Tracing n = 3: the array starts as [0, 0, 0, 0]. After dp[1] = 2 it is [0, 2, 0, 0]. The loop sets dp[2] = 4 and then dp[3] = 8, and the method returns 8.
Complexity
The loop runs n - 1 times with constant work each, so the time is O(n). The table has n + 1 entries, so the space is O(n). Because each entry depends only on the one before it, a single running variable would reduce the space to O(1). And since the answer is 2^n, 1 << n gives it in O(1) time, as the next section shows.
Edge cases and common mistakes
- Why the limit is 30. An
inttops out at 2,147,483,647.2^30is 1073741824 and fits, but2^31does not: the doubling wraps around to -2147483648 with no error. For a largern, uselong(up ton = 62) orBigInteger. n = 0. The statement allows zero, and there is exactly one string of length 0, the empty string. This reference solution does not handle it:new int[1]has only index 0, sodp[1] = 2throwsArrayIndexOutOfBoundsException. A table that starts atdp[0] = 1and loops from 1 works for everynfrom 0 up.- Off-by-one in the table size.
new int[n]would makedp[n]out of range. - Looping with
<. The loop would stop one entry short, anddp[n]would stay 0.
The shortest version
Since the answer is a power of two, a left shift computes it directly. Shifting 1 left by n places is 2^n:
static int countBinaryStrings(int n) {
return 1 << n;
}
It returns 1 for n = 0, 8 for n = 3 and 1073741824 for n = 30. The overflow limit is the same: 1 << 31 is -2147483648.
Generating the strings instead of counting them
Many people searching for this topic want the strings themselves, not their number. That is a different task, and a recursive method builds them: at each position try 0, then 1, and record the prefix once it reaches length n.
static void generate(int n, String prefix, List<String> out) {
if (prefix.length() == n) {
out.add(prefix);
return;
}
generate(n, prefix + "0", out);
generate(n, prefix + "1", out);
}
Calling it with n = 3, an empty prefix and an empty list fills the list with [000, 001, 010, 011, 100, 101, 110, 111]. This takes O(n * 2^n) time, because there are 2^n results and each one is n characters long, so it is only practical for small n.
