An existing problem goes that: Suppose we have two finite, ordered sequences x=(x1,…,xm) and y=(y1,…,yn). How many ways can we create a new sequence of length m+n from x and y so that the order of elements is preserved?
This new problem is different because we stress that there are elements appearing in both x and y. This differs from all existing problem which are either assume that x and y consist of different types of elements or accept that assumption without claiming it.
All answers I find adapt an assumption that x and y have no common elements, which leads to an easy closed form answer C(n+m,n).
However, things go messy if existence of common elements is allowed. Consider x=(1,2), y=(1,1). The number of ways would be 3 (1211,1121,1112), which makes the classic combination result fail.
I try using DP. Naturally, it goes that dp[i][j]=dp[i][j-1]+dp[i-1][j] when all elements are different. The inclusion-exclusion principle helps a special situation that the two strings (or substrings) are like ****ab and ****cb. We will have dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]. But it still works only on an extremely small subset of all the possible problems.
The title of this problem use "string" instead of "array" to stress the existence of common elements. I want to know that whether there is a P algorithm to solve this problem. Furthermore, you may assume that the set of characters is a limited constant; that means a "pseudo-P" algorithm is also good enough to be satisfying.
If you are confused about the concept of interleaving two strings, you may check a classic DP problem that requires verifying whether a string can be constructed by interleaving two other given strings.