Problem Link - Interleavings and Blocks
Problem Statement
Your task is the following. Given arrays A and B and a number K, find the number of different interleavings X of A and B that produce an output array C with exactly K blocks. Note that we are counting the number of interleavings, not the number of different output arrays after interleaving. For instance, if the same output array C is produced via 2 different interleavings, it gets counted twice.
Since the answer might be large, print the answer modulo 10^8 +7.
Here is a formal definition of the interleaving process:
Suppose A=A[1] ,A[2],...,A[n] and B=B[1], B[2],...,B[m]. Then, the process of generating an interleaving C can be described using an array X of size n+m, with exactly n~0′s and m~1′s. Suppose we have such an array X=X[1],X[2],...,X[n+m]. Using this array X, we create the output array C = C[1],C[2],...,C[n+m], using the following algorithm:
i = 0, j = 0
while( (i+j)<(n+m) )
if(X[i+j+1] == 0)
C[i+j+1] = A[i+1]
i = i+1
else
C[i+j+1] = B[j+1]
j = j+1
Thus if the X value is 0, we pick the next available element from A into C, and if it is 1, we pick from B instead. This creates an interleaving of the arrays A and B.
Approach
The problem can be solved using a dynamic programming approach. The main idea is to track the current position in arrays A and B, the number of blocks in the resulting interleaving so far, and the last array used to add an element. The recursive function tries two options at each step: adding the next element from A or from B. If the added element is different from the last one in the interleaved result, the block count is incremented. The base case occurs when all elements of both arrays are used, and the block count matches K. Memoization is used to store results for specific states to avoid redundant calculations. The solution ensures that every possible interleaving is considered and counted.
Time Complexity
The time complexity is O(n \times m \times k), where n and m are the lengths of A and B, and k is the number of blocks.
Space Complexity
The space complexity is O(n \times m \times k) due to the memoization table.