<p>You are given two integer arrays <code>nums1</code> and <code>nums2</code> of lengths <code>m</code> and <code>n</code> respectively. <code>nums1</code> and <code>nums2</code> represent the digits of two numbers. You are also given an integer <code>k</code>.</p>

<p>Create the maximum number of length <code>k &lt;= m + n</code> from digits of the two numbers. The relative order of the digits from the same array must be preserved.</p>

<p>Return an array of the <code>k</code> digits representing the answer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
<strong>Output:</strong> [9,8,6,5,3]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [6,7], nums2 = [6,0,4], k = 5
<strong>Output:</strong> [6,7,6,0,4]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [3,9], nums2 = [8,9], k = 3
<strong>Output:</strong> [9,8,9]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == nums1.length</code></li>
	<li><code>n == nums2.length</code></li>
	<li><code>1 &lt;= m, n &lt;= 500</code></li>
	<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 9</code></li>
	<li><code>1 &lt;= k &lt;= m + n</code></li>
</ul>

def createMaxNum(L,k):
    # returns maximum number one can make of all different lengths till k
    n = len(L)
    # Let A[i][j] be max numer one can make with subsequence of A[:i+1] of length j
    # A[i][j] = 0 if i+1 < j
    # A[i][0] = 0
    A = [[0]*(k+1) for i in range(n)]
    for j in range(1,k+1):
        for i in range(j-1,n):
            prev = A[i-1][j-1]
            x = 10*prev + L[i] #if L[i] is to be included
            y = A[i-1][j] # otherwise
            A[i][j] = max(x,y)
    return A[n-1]


def merge(A,B):
    n,m = len(A),len(B)
    if n == 0:return B
    if m == 0:return A
    C = []
    i = 0
    j = 0
    while i < n and j < m:
        I = i
        J = j
        while I < n and J < m and A[I] == B[J]:
            I += 1
            J += 1
        if I >= n and J < m:
            C.append(B[j])
            j += 1
        elif I < n and J >= m:
            C.append(A[i])
            i += 1
        elif I >= n and J >= m:
            C.append(A[i])
            i += 1
        elif A[I] > B[J]:
            C.append(A[i])
            i += 1
        elif A[I] < B[J]:
            C.append(B[j])
            j += 1
        else:
            raise ValueError()
    C.extend(A[i:])
    C.extend(B[j:])
    return C     

def solve(L1,L2,k):
    A = createMaxNum(L1,k)
    B = createMaxNum(L2,k)
    #print(A)
    #print(B)
    if len(L1)==0:
        return [int(x) for x in str(B[-1])]
    if len(L2)==0:
        return [int(x) for x in str(A[-1])]
    if L2 ==[0]*len(L2):
        return [int(x) for x in A[-1]] + L2
    if L1 ==[0]*len(L1):
        return [int(x) for x in B[-1]] + L1
    toret = [A[-1],B[-1]]
    for x in range(1,k):
        y = k - x
        if A[x]:a = list(str(A[x]))
        else: a = []
        if B[y]:b = list(str(B[y]))
        else: b = []
        c = merge(a,b)
        c = "".join(c)
        if c:c = int(c)
        else: c = 0
        toret.append(c)
    #print(toret)
    return max(toret)


class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        x = solve(nums1,nums2,k)
        x = [int(y) for y in str(x)]
        return x 
32500