<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>

class Solution {
    private:
        vector<int> helper(vector<int>& nums, int k){
            int n=nums.size();
            int j=0;
            vector<int> result(k,0);
            for(int i=0; i<n; i++){
                while(j>0 && n-i+j>k && nums[i]>result[j-1])  j--;
                if(j<k) result[j++]=nums[i];
            }
            return result;
        }
        
        vector<int> merge(vector<int>& nums1, vector<int>& nums2, int k){
            vector<int> result(k, 0);
            ostringstream num_str1, num_str2;
            string str1, str2;
            for(auto num:nums1)  num_str1 << num;
            for(auto num:nums2)  num_str2 << num;
            str1=num_str1.str();
            str2=num_str2.str();
            for(int i=0, j=0, r=0; r<k; r++){
                result[r] = str1.substr(i).compare(str2.substr(j)) > 0 ? nums1[i++] : nums2[j++];
            }
            return result;
        }
        
    public:
        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
            int n=nums1.size(), m=nums2.size();
            vector<int> result(k, 0);
            string result_str;
            for(int i=max(0, k-m); i<=k && i<=n; i++){
                vector<int> sub_1 = helper(nums1, i);
                vector<int> sub_2 = helper(nums2, k-i);
                vector<int> candidate = merge(sub_1, sub_2, k);
                ostringstream str_c;
                for(auto number:candidate)  str_c << number;
                if(result_str=="" || str_c.str().compare(result_str) > 0 ){
                    result_str=str_c.str();
                    result=candidate;
                }
            }
            return result;
        }
};
162702