1. Problem Statement

Given an integer n, we need to count the number of binary strings of length 2 * n such that:

For example, when n = 2, the valid strings are:

Code
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:

Code
1010

Prefix balances:

Code
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:

Code
0110

is invalid because its first prefix is:

Code
0

Here:

Code
ones = 0
zeros = 1

So the condition is violated.

3. Dynamic Programming Approach

We define:

Java
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:

Code
i ones
j zeros

There are two possibilities for the last character.

Case 1: Add 1

Before adding 1, we had:

Code
i - 1 ones
j zeros

So the number of ways is:

Code
dp[i - 1][j]

Case 2: Add 0

Before adding 0, we had:

Code
i ones
j - 1 zeros

So the number of ways is:

Code
dp[i][j - 1]

Therefore:

Code
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

However, we can only have:

Code
j <= i

because the number of zeros can never exceed the number of ones in any prefix.

4. Java Code

Java
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

Java
final int MOD = 1000000007;

The answer can become extremely large.

The problem asks us to return:

Code
answer % 1000000007

So we take modulo after every addition.

Step 2: DP Array

Java
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:

Code
dp[n + 1][n + 1]

which requires O(n²) memory.

But we only need the previous values, so we can optimize it to:

Code
O(n)

memory.

Step 3: Base Case

Java
dp[0] = 1;

There is exactly one way to construct an empty valid string:

Code
""

So:

Code
dp[0] = 1

Step 4: Process Ones

Java
for (int i = 1; i <= n; i++) {

Here i represents the number of 1s currently available.

For example:

Code
i = 1 → one 1
i = 2 → two 1s
i = 3 → three 1s
...

Step 5: Process Zeros

Java
for (int j = 1; j <= i; j++) {

We only process:

Code
j <= i

because zeros can never be greater than ones.

For example, if we have:

Code
i = 3

we can have:

Code
j = 1
j = 2
j = 3

But we cannot have:

Code
j = 4

because that would mean more zeros than ones.

Step 6: DP Transition

Java
dp[j] = (dp[j] + dp[j - 1]) % MOD;

This is the most important line.

The two values represent:

Code
dp[j]     → ways from adding a 1
dp[j - 1] → ways from adding a 0

Therefore:

Code
new dp[j] = old dp[j] + old dp[j - 1]

6. Dry Run for n = 3

Initially:

Code
dp = [1, 0, 0, 0]

i = 1

j = 1

Code
dp[1] = dp[1] + dp[0]
      = 0 + 1
      = 1

Now:

Code
dp = [1, 1, 0, 0]

i = 2

For j = 1:

Code
dp[1] = dp[1] + dp[0]
      = 1 + 1
      = 2

For j = 2:

Code
dp[2] = dp[2] + dp[1]
      = 0 + 2
      = 2

Now:

Code
dp = [1, 2, 2, 0]

i = 3

For j = 1:

Code
dp[1] = 2 + 1 = 3

For j = 2:

Code
dp[2] = 2 + 3 = 5

For j = 3:

Code
dp[3] = 0 + 5 = 5

Final:

Code
dp = [1, 3, 5, 5]

Therefore:

Java
return (int) dp[3];

returns:

Code
5

7. Why Is the Answer 5?

For n = 3, we need three 1s and three 0s.

The valid strings are:

Code
111000
110100
110010
101100
101010

There are:

Code
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:

Code
n = 0 → 1
n = 1 → 1
n = 2 → 2
n = 3 → 5
n = 4 → 14
n = 5 → 42

So:

Code
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:

Code
100

Prefix balances:

Code
1    → 1 one, 0 zeros
10   → 1 one, 1 zero
100  → 1 one, 2 zeros

At the last prefix:

Code
ones = 1
zeros = 2

Therefore:

Code
ones < zeros

The string is invalid.

Our DP prevents this situation by only calculating states where:

Code
zeros <= ones

which is:

Java
j <= i

10. Why Use long?

We use:

Java
long[] dp

instead of:

Java
int[] dp

because the intermediate addition can be larger than the range of an int before modulo is applied.

This:

Java
dp[j] + dp[j - 1]

is therefore safely calculated using long.

Then we return:

Java
(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:

Code
1 + 2 + 3 + ... + n = O(n²)

Time Complexity

Code
O(n²)

Space Complexity

We only maintain:

Java
long[] dp

of size n + 1.

Therefore:

Code
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:

Code
dp[i][j] = dp[i-1][j] + dp[i][j-1]

with the restriction:

Code
j <= i

We then optimize the 2D DP into a 1D array.

The final value:

Java
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.