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

vector<int> maxseq(map<int, set<int>> &mp, int index, int len, int k){
    
    if(k> len){
        return {-1};
    }
    if(k==0){
        return {};
    }
    if(k==1){
        for(int i=9; i>0; i--){
            if(mp.find(i)!= mp.end()){
                
                auto it = mp[i].upper_bound(index);

                if(it!=mp[i].end()){

                    return {i};
                }
            }
        }
    }
    for(int i=9; i>=0; i--){
        if(mp.find(i)!=mp.end()){
            auto it = mp[i].upper_bound(index);
            if(it!= mp[i].end()){
                
                if(*it <= len - k){
                    // cout<<i<<" "<<index<<" "<<*it<<" "<<len<<" "<<k<<endl;
                    vector<int> a = maxseq(mp, *it, len, k-1);
                    a.push_back(i);
                    return a;

                }
            }
        }
    }
    return {-1};
}
bool comp(int i, int j, vector<int> &a, vector<int> &b){
    int aptr = i;
    int bptr = j;
    while(aptr < a.size() && bptr < b.size()){
        if(a[aptr] > b[bptr]){
            return 0;
        }else if(a[aptr] < b[bptr]){
            return 1;
        }
        else{
            aptr++;
            bptr++;
        }
    }
    if(aptr == a.size() && bptr!= b.size()){
        return 1;
    }else if(bptr == b.size() && aptr!= a.size()){
        return 0;
    }
    return 1;
}
vector<int> merge(vector<int> &a, vector<int> &b){
    int aptr = 0;
    int bptr = 0;
    vector<int> ans;
    while(aptr < a.size() || bptr < b.size()){
        if(aptr == a.size()){
            ans.push_back(b[bptr]);
            bptr++;
        }else if(bptr == b.size()){
            ans.push_back(a[aptr]);
            aptr++;
        }else{
            if(a[aptr] > b[bptr]){
                ans.push_back(a[aptr]);
                aptr++;
            }else if(a[aptr] < b[bptr]){
                ans.push_back(b[bptr]);
                bptr++;
            }else{
                bool f = comp(aptr, bptr, a, b);
                if(f){
                    ans.push_back(b[bptr]);
                    bptr++;
                }else{
                    ans.push_back(a[aptr]);
                    aptr++;
                }
            }
        }
    }
    return ans;
}
bool cmp(vector<int> &a, vector<int> &b){
   
    for(int i=0; i<a.size(); i++){
        if(a[i] < b[i]){
            return 0;
        }
        else if(a[i] > b[i]){
            return 1;
        }
    }
    return 0;
}
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        map<int, set<int>> mp1;
        map<int, set<int>> mp2;
        for(int i=0; i<nums1.size(); i++){
            mp1[nums1[i]].insert(i);
        }
        for(int i=0; i<nums2.size(); i++){
            mp2[nums2[i]].insert(i);
        }
        vector<int> ans(k);
        for(int i=0; i<=k; i++){
            vector<int> a = maxseq(mp1, -1, nums1.size(), i);
            if(a.size() > 0){
                if(a[0]==-1){
                    continue;
                }
                
            }
            vector<int> b = maxseq(mp2, -1, nums2.size(), k-i);
            if(b.size() > 0){
                if(b[0] == -1){
                    continue;
                }
            }
            reverse(a.begin(), a.end());
            reverse(b.begin(), b.end());
            vector<int> tans = merge(a, b);
            bool f = cmp(tans, ans);
            if(f==1){
                ans = tans;
            }
        }
        return ans;

        



    }
};
43497