# Maximize interleaving subsequences two digit arrays/strings

Suppose I have two digit arrays, A and B as follows

A = [3,4,5,6]
B = [9,8,3]


Now, I have to interleave the two arrays which would mean to pop the first element from both the arrays, at any given point of time. One such interleaving would be as follows,

Choose 3 from A
A = [4,5,6]
B = [9,8,3]
Choose 9 from B
A = [4,5,6]
B = [8,3]
Choose 4 from A
A = [5,6]
B = [8,3]
Choose 8 from B
A = [5,6]
B = [3]
Choose 5 from A
A = [6]
B = [3]
Choose 3 from B
A = [6]
B = []
Choose 6 from A
A = []
B = []
Output array = [3,9,4,8,5,3,6]


In other words, one can choose elements from both A and B but will have to be chosen sequentially.

Now, the question is how can one produce the array that is maximal. In this case, the maximal number would be [9,8,3,4,5,6,3].

P.S. I have already come up about how to solve this with dynamic programming, with the time complexity of $$O(mn)$$(Here $$n$$ and $$m$$ are the lengths of the arrays A and B respectively. But I am actually looking for something more effective(maybe linear time?). The tricky situation is when choosing elements that are equal, and that is where one can optimize. Here I have assumed digits, but each of the arrays could be a separate string as well.

• Is $n$ = length(A) and $m$ = length(B)? Please mention in the question that at any point in time, you have to "pop" the first element of one of the two arrays (whichever leads to the optimal solution) and that [9,8,3,4,5,6,3] represents the number 9834563. Can it only be decimal digits ((0?), 1-9)? – Albert Hendriks Dec 22 '18 at 22:40
• Think of this as arrays. You could interpret popping an element as selecting the first element from any of those arrays and then advancing the iterator for the array which the first element is selected. I haven't mentioned lists or linked lists anywhere. Also, please see this for a similar question - leetcode.com/problems/interleaving-string – Palash Ahuja Dec 27 '18 at 20:09
• I am writing my code of $O(n)$ time-complexity. It takes lots of time as I cannot simplify the many cases with the equal elements well yet. – John L. Dec 28 '18 at 6:53