Largest Merge of Two Strings: Greedy Suffix Comparison

LeetCode Largest Merge of Two Strings (problem 1754) asks you to build the lexicographically largest string possible by repeatedly taking one character from the front of either word1 or word2. At each step you choose which string to pull from, and the goal is to maximize the result.

Why this problem matters

This problem teaches you to think about greedy decisions that depend on future context, not just the current character. At first glance, it seems like you should always pick the larger front character. But what happens when both front characters are the same? The tiebreaker requires looking deeper into both strings, and that is where the suffix comparison insight comes in.

The pattern of "compare remaining suffixes to break ties" shows up in problems involving lexicographic optimization, string construction, and greedy scheduling. Once you internalize it, you can apply it to any problem where a local greedy choice needs global context to be correct.

The key insight

At each step, compare the remaining suffix of word1 (from index i onward) with the remaining suffix of word2 (from index j onward). If word1[i:] is lexicographically greater than or equal to word2[j:], take the character from word1. Otherwise, take from word2.

Why suffixes and not just the front characters? Consider word1 = "ab" and word2 = "aa". Both start with 'a', but taking from word1 first gives "a" + merge("b", "aa") = "abaa", while taking from word2 first gives "a" + merge("ab", "a") = "aaba". The suffix "ab" > "aa" correctly tells you to take from word1.

The algorithm is:

1. Initialize two pointers i = 0 and j = 0, and an empty result.
2. While both pointers are in bounds, compare word1[i:] with word2[j:].
3. If word1[i:] >= word2[j:], append word1[i] and increment i.
4. Otherwise, append word2[j] and increment j.
5. Append whatever remains of the non-exhausted string.

The solution

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

The loop runs until one string is exhausted. At each iteration, the suffix comparison word1[i:] >= word2[j:] determines which character to take. Python's string comparison is lexicographic by default, so this single expression handles both the "different first character" case and the "same first character, need to look deeper" case. After the loop, the remaining portion of whichever string still has characters is appended directly.

Visual walkthrough

Let's trace through the algorithm with word1 = "cabaa" and word2 = "bcafc". At each step, we compare the remaining suffixes and take the character from the larger one.

Notice how in step 4, both suffixes start with 'a', but the comparison looks deeper: "abaa" vs "afc". Since 'b' < 'f' at the second position, "afc" wins, and we take from word2. This is exactly the kind of tiebreaker that a naive "compare only the front character" approach would get wrong.

Complexity analysis

Time: The loop runs m + n times (once per character added to the merge). Each iteration performs a suffix comparison that can take up to O(m + n) in the worst case, giving O((m + n)^2) overall. In practice, the comparisons are often short because the suffixes diverge quickly.

Space: The merge result is m + n characters long, and the suffix slices are temporary. Total space is O(m + n).

The building blocks

1. Lexicographic suffix comparison for greedy decisions

The core pattern is using suffix comparison to make a greedy choice:

if word1[i:] >= word2[j:]:
    take_from_word1()
else:
    take_from_word2()

This pattern applies whenever you need to build a lexicographically optimal result by choosing between two sources. The suffix comparison ensures you account for all future characters, not just the immediate one. The same thinking appears in problems like Remove Duplicate Letters, where you need to decide whether to keep or discard a character based on what comes later.

2. Two-pointer merge with a custom comparator

The overall structure follows the classic two-pointer merge pattern, but instead of always taking the smaller element (as in merge sort), you take the larger one and use suffix comparison as the tie-breaking rule:

i, j = 0, 0
while i < len(a) and j < len(b):
    if compare(a, i, b, j):
        result.append(a[i]); i += 1
    else:
        result.append(b[j]); j += 1
result.append(a[i:])
result.append(b[j:])

This skeleton is reusable for any merge-based construction problem where the comparison logic changes. Swap compare for your specific criterion and the structure stays identical.

Edge cases

• One string is empty. If word1 is empty, the merge is just word2, and vice versa. The algorithm handles this because the while loop does not execute and the remaining string is appended.
• Identical strings. If word1 == word2, every suffix comparison is a tie (equal), so you always take from word1. The result is the interleaving where word1 characters come first at each tie.
• One string is a prefix of the other. For example, word1 = "aaa" and word2 = "aab". The suffix comparison correctly prefers word2 when it matters, because "aab" > "aaa".
• Single character strings. word1 = "z", word2 = "a". One comparison, take 'z' first, then 'a'. Result is "za".
• All same characters. word1 = "aaa", word2 = "aaa". All suffixes are equal, so you alternate taking from word1 first. Result is "aaaaaa".

From understanding to recall

The algorithm is short, but the insight behind it is subtle. You need to remember that comparing just the front characters is not enough, and that full suffix comparison is the correct tiebreaker. That is the piece that fades from memory without practice.

When you review this problem, focus on the "why" behind suffix comparison. Ask yourself: what goes wrong if I only compare word1[i] vs word2[j]? Think through a case where both characters are equal but the suffixes diverge. That mental exercise reinforces the core insight more than memorizing the code.

Then write the solution from scratch. The two-pointer loop, the suffix comparison, and the final append of the remaining string should feel like one fluid pattern. Spaced repetition ensures you practice this at increasing intervals until the pattern is automatic, not something you have to rederive under interview pressure.

Related posts

• Merge Sorted Array - The foundational merge pattern
• Orderly Queue - String reordering with lexicographic goals
• Remove Duplicate Letters - Greedy string construction for lexicographic optimality

CodeBricks breaks the largest merge of two strings problem into its suffix comparison and two-pointer merge building blocks, then drills them independently with spaced repetition. You type each pattern from scratch until it is automatic. When a greedy string construction question shows up in your interview, you write the solution without hesitation.