Problem statement

You are given two strings word1 and word2. Build a string merge by repeating the following until both words are empty: take the first character of word1 or of word2 (whichever you like, as long as that word is non-empty), remove it from that word and append it to merge.

Every character of both words ends up in merge exactly once, and each word's characters keep their relative order.

Return the lexicographically largest merge you can build. A string x is larger than a string y of the same length if, at the first position where they differ, x has the later letter.

Example 1

Input: word1 = "kairo", word2 = "code"
Output: kcodeairo
Explanation: Take `k` first; after that every letter of `code` beats the `a` waiting in `word1`, so all of `code` goes before `airo`.

Example 2

Input: word1 = "ab", word2 = "ac"
Output: acab
Explanation: Both fronts are `a`. Taking it from `word2` exposes `c` next, which beats `b`.

Example 3

Input: word1 = "abc", word2 = "abd"
Output: abdabc

Constraints

• 1 <= word1.length, word2.length <= 3000
• word1 and word2 consist only of lowercase English letters

Hints for Largest Merge Of Two Strings

1. Hint 1

   Comparing only the two front characters fails when they are equal — you need a tie-break.

2. Hint 2

   When the fronts tie, look further: the word whose remaining suffix is larger should give up its character first.

3. Hint 3

   At every step take the front of the word whose whole remaining suffix is lexicographically larger; when one word runs out, append the rest of the other.

How to solve Largest Merge Of Two Strings

Greedy on suffixes: at each step take the front character of the word whose remaining suffix is lexicographically larger.

Approach

1. Keep indices i into word1 and j into word2.
2. While both have characters left, compare the suffixes word1[i:] and word2[j:]. If word1[i:] is larger, append word1[i] and advance i; otherwise append word2[j] and advance j.
3. Append whatever is left of either word.

Why it works

If the fronts differ, taking the larger one is clearly right. If they are equal, the character appended is the same either way, but the choice decides which word's later characters become available sooner. Taking from the word with the larger suffix exposes the larger continuation earlier; an exchange argument shows any merge that took from the smaller suffix can be rearranged into one at least as large that follows the greedy choice. Comparing whole suffixes handles long runs of equal characters and the case where one suffix is a prefix of the other (the longer one is larger, and drawing from it keeps the shorter one's characters in reserve).

Complexity

• Time — O((n + m)^2) in the worst case, from the suffix comparisons
• Space — O(n + m) for the result

Pitfalls

• Breaking a tie of equal front characters arbitrarily is wrong: for word1 = "ab" and word2 = "ac" you must take the a of word2 first to reach acab.
• When one suffix is a prefix of the other, the longer suffix compares larger — standard string comparison already does this.
• Build the answer with a string builder or list; repeated string concatenation can be quadratic in some languages.

Reference solution

Python

def largestMerge(word1: str, word2: str) -> str:
    i, j = 0, 0
    out = []
    while i < len(word1) and j < len(word2):
        if word1[i:] > word2[j:]:
            out.append(word1[i])
            i += 1
        else:
            out.append(word2[j])
            j += 1
    out.append(word1[i:])
    out.append(word2[j:])
    return "".join(out)

Java

public static String largestMerge(String word1, String word2) {
    StringBuilder sb = new StringBuilder();
    int i = 0, j = 0;
    while (i < word1.length() && j < word2.length()) {
        if (word1.substring(i).compareTo(word2.substring(j)) > 0) sb.append(word1.charAt(i++));
        else sb.append(word2.charAt(j++));
    }
    sb.append(word1.substring(i)).append(word2.substring(j));
    return sb.toString();
}

C++

string largestMerge(string word1, string word2) {
    string out;
    size_t i = 0, j = 0;
    while (i < word1.size() && j < word2.size()) {
        if (word1.compare(i, string::npos, word2, j, string::npos) > 0) out += word1[i++];
        else out += word2[j++];
    }
    out += word1.substr(i);
    out += word2.substr(j);
    return out;
}

JavaScript

var largestMerge = function(word1, word2) {
    var i = 0, j = 0, out = [];
    while (i < word1.length && j < word2.length) {
        if (word1.slice(i) > word2.slice(j)) out.push(word1[i++]);
        else out.push(word2[j++]);
    }
    return out.join("") + word1.slice(i) + word2.slice(j);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Merge Two Sorted Linked Lists in Reverse Order Medium
• Rotate a Linked List Medium
• Segregate Even and Odd Nodes in a Linked List Medium
• Maximum Twin Sum of a Linked List Medium
• Delete the Middle Node of a Linked List Medium
• Swapping Nodes in a Linked List Medium