1. Problem Statement
Given an integer n, we need to count the number of binary strings of length 2 * n such that:
The string contains exactly n ones (1).
The string contains exactly n zeros (0).
In every prefix of the string, the number of 1s is greater than or equal to the number of 0s.
Return the answer modulo 10^9 + 7.
For example, when n = 2, the valid strings are:
1100
1010
Therefore, the answer is 2.
2. Important Observation
The condition:
Every prefix must contain at least as many 1s as 0s.
means that we can think of:
We are never allowed to use more 0s than 1s at any point.
For example:
1010
Prefix balances:
1 → ones = 1, zeros = 0
10 → ones = 1, zeros = 1
101 → ones = 2, zeros = 1
1010 → ones = 2, zeros = 2
The balance never becomes negative.
But:
0110
is invalid because its first prefix is:
0
Here:
ones = 0
zeros = 1
So the condition is violated.
3. Dynamic Programming Approach
We define:
dp[j]
as the number of valid ways to construct the current string using j zeros.
We process the number of 1s one by one.
Suppose we have used:
i ones
j zeros
There are two possibilities for the last character.
Case 1: Add 1
Before adding 1, we had:
i - 1 ones
j zeros
So the number of ways is:
dp[i - 1][j]
Case 2: Add 0
Before adding 0, we had:
i ones
j - 1 zeros
So the number of ways is:
dp[i][j - 1]
Therefore:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
However, we can only have:
j <= i
because the number of zeros can never exceed the number of ones in any prefix.
4. Java Code
class Solution {
public int prefixStrings(int n) {
final int MOD = 1000000007;
long[] dp = new long[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[j] = (dp[j] + dp[j - 1]) % MOD;
}
}
return (int) dp[n];
}
}
5. Code Explanation
Step 1: Modulo
final int MOD = 1000000007;
The answer can become extremely large.
The problem asks us to return:
answer % 1000000007
So we take modulo after every addition.
Step 2: DP Array
long[] dp = new long[n + 1];
We use a one-dimensional array instead of a two-dimensional DP table.
A normal 2D solution would require:
dp[n + 1][n + 1]
which requires O(n²) memory.
But we only need the previous values, so we can optimize it to:
O(n)
memory.
Step 3: Base Case
dp[0] = 1;
There is exactly one way to construct an empty valid string:
""
So:
dp[0] = 1
Step 4: Process Ones
for (int i = 1; i <= n; i++) {
Here i represents the number of 1s currently available.
For example:
i = 1 → one 1
i = 2 → two 1s
i = 3 → three 1s
...
Step 5: Process Zeros
for (int j = 1; j <= i; j++) {
We only process:
j <= i
because zeros can never be greater than ones.
For example, if we have:
i = 3
we can have:
j = 1
j = 2
j = 3
But we cannot have:
j = 4
because that would mean more zeros than ones.
Step 6: DP Transition
dp[j] = (dp[j] + dp[j - 1]) % MOD;
This is the most important line.
The two values represent:
dp[j] → ways from adding a 1
dp[j - 1] → ways from adding a 0
Therefore:
new dp[j] = old dp[j] + old dp[j - 1]
6. Dry Run for n = 3
Initially:
dp = [1, 0, 0, 0]
i = 1
j = 1
dp[1] = dp[1] + dp[0]
= 0 + 1
= 1
Now:
dp = [1, 1, 0, 0]
i = 2
For j = 1:
dp[1] = dp[1] + dp[0]
= 1 + 1
= 2
For j = 2:
dp[2] = dp[2] + dp[1]
= 0 + 2
= 2
Now:
dp = [1, 2, 2, 0]
i = 3
For j = 1:
dp[1] = 2 + 1 = 3
For j = 2:
dp[2] = 2 + 3 = 5
For j = 3:
dp[3] = 0 + 5 = 5
Final:
dp = [1, 3, 5, 5]
Therefore:
return (int) dp[3];
returns:
5
7. Why Is the Answer 5?
For n = 3, we need three 1s and three 0s.
The valid strings are:
111000
110100
110010
101100
101010
There are:
5
valid strings.
8. Connection With Catalan Numbers
This problem is a classic Catalan Number problem.
The number of prefix-balanced binary strings with n ones and n zeros is:
$$
C_n = \frac{1}{n+1}\binom{2n}{n}
$$
The first few Catalan numbers are:
n = 0 → 1
n = 1 → 1
n = 2 → 2
n = 3 → 5
n = 4 → 14
n = 5 → 42
So:
n = 2 → 2
n = 3 → 5
matches the examples.
Although we could calculate the answer directly using the Catalan formula, the problem specifically expects Dynamic Programming, so the DP solution is a good fit.
9. Why Do We Need j <= i?
This is the key condition.
Consider:
100
Prefix balances:
1 → 1 one, 0 zeros
10 → 1 one, 1 zero
100 → 1 one, 2 zeros
At the last prefix:
ones = 1
zeros = 2
Therefore:
ones < zeros
The string is invalid.
Our DP prevents this situation by only calculating states where:
zeros <= ones
which is:
j <= i
10. Why Use long?
We use:
long[] dp
instead of:
int[] dp
because the intermediate addition can be larger than the range of an int before modulo is applied.
This:
dp[j] + dp[j - 1]
is therefore safely calculated using long.
Then we return:
(int) dp[n]
because the final value has already been reduced modulo 1000000007.
11. Complexity
The outer loop runs n times.
The inner loop runs up to i times.
Therefore:
1 + 2 + 3 + ... + n = O(n²)
Time Complexity
O(n²)
Space Complexity
We only maintain:
long[] dp
of size n + 1.
Therefore:
O(n)
This exactly matches the expected complexity.
Final Takeaway
The main idea to remember is:
Treat 1 as increasing the balance and 0 as decreasing it. A valid string must never have a negative balance.
In DP terms:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
with the restriction:
j <= i
We then optimize the 2D DP into a 1D array.
The final value:
dp[n]
gives the number of prefix-balanced binary strings containing exactly n ones and n zeros.
Summary
This problem can be solved efficiently using Dynamic Programming. The important condition is that the number of 0s must never become greater than the number of 1s in any prefix. By keeping track of the number of ones and zeros used and ignoring invalid states where zeros > ones, we can count all valid strings. The 1D DP implementation uses O(n²) time and O(n) space, while the resulting values correspond to the well-known Catalan numbers.