You are given two strings word1 and word2. You want to construct a string merge in the following way: while either word1 or word2 are non-empty, choose one of the following options:


	If word1 is non-empty, append the first character in word1 to merge and delete it from word1.

	
		For example, if word1 = "abc" and merge = "dv", then after choosing this operation, word1 = "bc" and merge = "dva".
	
	
	If word2 is non-empty, append the first character in word2 to merge and delete it from word2.
	
		For example, if word2 = "abc" and merge = "", then after choosing this operation, word2 = "bc" and merge = "a".
	
	


Return the lexicographically largest merge you can construct.

A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b. For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.

&nbsp;
Example 1:

Input: word1 = "cabaa", word2 = "bcaaa"
Output: "cbcabaaaaa"
Explanation: One way to get the lexicographically largest merge is:
- Take from word1: merge = "c", word1 = "abaa", word2 = "bcaaa"
- Take from word2: merge = "cb", word1 = "abaa", word2 = "caaa"
- Take from word2: merge = "cbc", word1 = "abaa", word2 = "aaa"
- Take from word1: merge = "cbca", word1 = "baa", word2 = "aaa"
- Take from word1: merge = "cbcab", word1 = "aa", word2 = "aaa"
- Append the remaining 5 a's from word1 and word2 at the end of merge.


Example 2:

Input: word1 = "abcabc", word2 = "abdcaba"
Output: "abdcabcabcaba"


&nbsp;
Constraints:


	1 &lt;= word1.length, word2.length &lt;= 3000
	word1 and word2 consist only of lowercase English letters.


class Solution:
    def largestMerge(self, word1: str, word2: str) -> str:
        res = ''
        p1 = 0
        p2 = 0
        while p1 < len(word1) and p2 < len(word2):
            if word1[p1:] > word2[p2:]:
                res += word1[p1]
                p1 += 1
            else:
                res += word2[p2]
                p2 += 1
        
        res += word1[p1:] + word2[p2:]

        
        return res
class Solution {
    public String largestMerge(String word1, String word2) {
        StringBuilder sb = new StringBuilder();
        int i=0;
        int j=0;
        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        
        int n1=w1.length;
        int n2=w2.length;
        
        // we loop until we exhaust any one of the 2 words completely
        while(i<n1 && j<n2){
            
            // if both the characters are equal we choose the one where the next largest occurs earlier
            if(w1[i]==w2[j]){
                if(check(w1,i,w2,j)){
                    sb.append(w1[i++]);
                }else{
                    sb.append(w2[j++]);
                }
            }
            
            // else we greedily choose the largest of the two characters
            else if(w1[i]>w2[j]){
                sb.append(w1[i++]);
            }else{
                sb.append(w2[j++]);
            }
        }
        
        // at the end of the loop we append any remaining word
        sb.append(word1.substring(i));
        sb.append(word2.substring(j));
		
        return sb.toString();
    }
    
    private boolean check(char[] w1, int i, char[] w2, int j){
        // will return true if we need to extract from word1 and false if we need to extract from word2
        
        while(i<w1.length && j<w2.length){
            if(w1[i]==w2[j]){
                i++;
                j++;
            }
            else if(w1[i]>w2[j]){
                return true;
            }else{
                return false;
            }
        }
        
        // if we are unable to find any exhaustable character till the end of the loop we use the one having larger length
        if(i<w1.length){
            return true;
        }
        return false;
    }
}
class Solution {
public:
    string largestMerge(string word1, string word2) {
        
        string ans="";
        
        while(word1.size()!=0 && word2.size()!=0){
            if(word1>=word2) {ans+=word1[0];word1=word1.substr(1);}
            
            else             {ans+=word2[0];word2=word2.substr(1);}
        }
        
        if(word1.size()!=0)ans=ans+word1;
        if(word2.size()!=0)ans=ans+word2;
        
        return ans;
    }
};
var largestMerge = function(word1, word2) {
    let ans = '';
    let w1 = 0, w2 = 0;

    while(w1 < word1.length && w2 < word2.length) {
        if(word1[w1] > word2[w2]) ans += word1[w1++];
        else if(word2[w2] > word1[w1]) ans += word2[w2++];
        else {
            const rest1 = word1.slice(w1);
            const rest2 = word2.slice(w2);

            if(rest1 > rest2) ans += word1[w1++];
            else ans += word2[w2++];
        }
    }
    ans += word1.slice(w1);
    ans += word2.slice(w2);
    return ans;
};
Largest Merge Of Two Strings