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:

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.