LeetCode 1754 - Largest Merge Of Two Strings

LeetCode Problem 1754

Difficulty: 🟡 Medium
Topics: Two Pointers, String, Greedy

Solution

Problem Understanding

This problem asks us to build the lexicographically largest possible string by repeatedly choosing characters from the front of two given strings. At every step, we may take the first character from either word1 or word2, append it to the result, and remove it from its original string.

The important detail is that we are not allowed to reorder characters inside either string. We can only consume characters from left to right. This means the final merge must preserve the relative order of characters from each original word.

The goal is not simply to create any valid merge, but specifically the lexicographically largest one. Lexicographical comparison works similarly to dictionary ordering. When comparing two strings, we look at the first position where they differ. The string with the larger character at that position is considered larger.

For example:

• "cab" is larger than "caa" because 'b' > 'a'
• "abc" is smaller than "abd" because 'c' < 'd'

The constraints are important:

• 1 <= word1.length, word2.length <= 3000
• Only lowercase English letters are used

The maximum combined length is 6000, which is small enough for quadratic solutions, but too large for exponential brute force approaches.

Several edge cases are important to think about early:

• One string may become empty before the other
• The current leading characters of both strings may be equal
• Long common prefixes can occur, forcing deeper comparisons
• One string may be a prefix of the other, such as "abc" and "abcde"

These cases make naive greedy strategies dangerous. Simply choosing the larger current character is not enough when the characters are equal.

Approaches

Brute Force Approach

A brute force solution would try every possible valid merge. At each step, if both strings are non-empty, we branch into two recursive possibilities:

• Take the first character from word1
• Take the first character from word2

We then generate every possible merge and return the lexicographically largest one.

This approach is correct because it exhaustively explores the entire decision tree. Every valid merge is considered, so the optimal answer is guaranteed to be found.

However, the number of possible merges grows exponentially. If the total length is n + m, the number of interleavings is:

$$\binom{n+m}{n}$$

This becomes enormous even for moderate input sizes. With lengths up to 3000, brute force is completely infeasible.

Optimal Greedy Approach

The key observation is that when deciding which character to take next, we should compare the remaining suffixes of the two strings.

Suppose we are currently looking at:

• word1[i:]
• word2[j:]

If word1[i:] is lexicographically larger than word2[j:], then taking from word1 immediately gives a better result. Otherwise, we should take from word2.

This works because the current decision determines the earliest differing position in the final merge, which dominates lexicographical ordering.

A subtle but crucial point is handling equal leading characters. Consider:

• word1 = "abz"
• word2 = "abc"

The first characters are both 'a'. We cannot decide based only on the current character. We must compare the remaining suffixes:

• "abz" > "abc"

So we should take from word1.

This transforms the problem into a clean greedy strategy based on suffix comparison.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all possible merges
Optimal	O((n + m)^2)	O(n + m)	Greedily compares remaining suffixes

Algorithm Walkthrough

1. Initialize two indices, one for each string.

Let:

• i track the current position in word1
• j track the current position in word2

Also create a result list to efficiently build the final string. 2. Continue while both strings still contain characters.

At each step, compare:

• word1[i:]
• word2[j:]

These are the remaining suffixes. 3. If word1[i:] is lexicographically larger, append word1[i] to the result.

Then increment i.

This is optimal because the suffix comparison guarantees that choosing from word1 produces a larger final merge. 4. Otherwise, append word2[j] to the result.

Then increment j. 5. Once one string is exhausted, append all remaining characters from the other string.

Since there is no longer any choice to make, the remainder must be appended directly. 6. Join the result list into a final string and return it.

Why it works

The greedy choice is always safe because lexicographical ordering is determined by the earliest differing position. At every step, comparing the remaining suffixes tells us which choice creates a larger future string. By always selecting the lexicographically larger suffix, we guarantee that the earliest possible differing character in the final merge is maximized. This invariant holds throughout the entire process, proving correctness.

Python Solution

class Solution:
    def largestMerge(self, word1: str, word2: str) -> str:
        i = 0
        j = 0

        merge = []

        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 implementation follows the greedy algorithm directly.

The variables i and j track our current position inside each string. Instead of repeatedly creating new strings by concatenation, we store characters inside the list merge. This is more efficient because Python string concatenation inside loops can become expensive.

Inside the main loop, we compare the remaining suffixes:

word1[i:] > word2[j:]

Python performs lexicographical comparison automatically for strings, which makes the implementation extremely concise.

If the remaining suffix of word1 is larger, we take the next character from word1. Otherwise, we take from word2.

After the loop finishes, one string has been fully consumed. The remaining substring from the other word is appended directly.

Finally, "".join(merge) converts the list into the final result string.

Go Solution

func largestMerge(word1 string, word2 string) string {
    i := 0
    j := 0

    result := make([]byte, 0, len(word1)+len(word2))

    for i < len(word1) && j < len(word2) {
        if word1[i:] > word2[j:] {
            result = append(result, word1[i])
            i++
        } else {
            result = append(result, word2[j])
            j++
        }
    }

    for i < len(word1) {
        result = append(result, word1[i])
        i++
    }

    for j < len(word2) {
        result = append(result, word2[j])
        j++
    }

    return string(result)
}

The Go implementation is very similar to the Python version, but there are some language-specific differences.

Instead of using a dynamic string builder through concatenation, we use a []byte slice to efficiently build the result. This avoids repeated string allocations.

Go also supports lexicographical comparison between strings using the > operator, so suffix comparison remains simple:

word1[i:] > word2[j:]

Unlike Python, Go does not allow appending entire substrings directly into a byte slice, so we use loops to append the remaining characters after one string is exhausted.

There are no integer overflow concerns because indices never exceed 6000.

Worked Examples

Example 1

Input:

word1 = "cabaa"
word2 = "bcaaa"

Step	word1 Remaining	word2 Remaining	Chosen	Merge
1	cabaa	bcaaa	c from word1	c
2	abaa	bcaaa	b from word2	cb
3	abaa	caaa	c from word2	cbc
4	abaa	aaa	a from word1	cbca
5	baa	aaa	b from word1	cbcab
6	aa	aaa	a from word2	cbcaba
7	aa	aa	a from word2	cbcabaa
8	aa	a	a from word1	cbcabaaa
9	a	a	a from word2	cbcabaaaa
10	a	empty	a from word1	cbcabaaaaa

Final answer:

"cbcabaaaaa"

Example 2

Input:

word1 = "abcabc"
word2 = "abdcaba"

Step	word1 Remaining	word2 Remaining	Chosen	Merge
1	abcabc	abdcaba	a from word2	a
2	abcabc	bdcaba	b from word2	ab
3	abcabc	dcaba	d from word2	abd
4	abcabc	caba	c from word2	abdc
5	abcabc	aba	a from word1	abdca
6	bcabc	aba	b from word1	abdcab
7	cabc	aba	c from word1	abdcabc
8	abc	aba	a from word1	abdcabca
9	bc	ba	b from word2	abdcabcab
10	bc	a	b from word1	abdcabcabb
11	c	a	c from word1	abdcabcabbc
12	empty	a	a from word2	abdcabcabbca
13	empty	ba	b from word2	abdcabcabbcab
14	empty	a	a from word2	abdcabcabbcaba

Final answer:

"abdcabcabcaba"

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + m)^2)	Suffix comparisons may scan many characters repeatedly
Space	O(n + m)	Result storage

The main cost comes from comparing suffixes like:

word1[i:] > word2[j:]

Each comparison may take linear time in the worst case, especially when long prefixes are equal. Since we perform up to n + m comparisons, the overall worst-case complexity becomes quadratic.

The auxiliary space complexity is linear because the output itself contains n + m characters.

Test Cases

solution = Solution()

assert solution.largestMerge("cabaa", "bcaaa") == "cbcabaaaaa"  # Provided example
assert solution.largestMerge("abcabc", "abdcaba") == "abdcabcabcaba"  # Provided example

assert solution.largestMerge("a", "b") == "ba"  # Single-character strings
assert solution.largestMerge("z", "a") == "za"  # Larger first character

assert solution.largestMerge("abc", "abc") == "abcabc"  # Identical strings
assert solution.largestMerge("aaa", "aaa") == "aaaaaa"  # Repeated equal characters

assert solution.largestMerge("abz", "abc") == "abzabc"  # Deep suffix comparison
assert solution.largestMerge("guguuuuuuuuuuuuuugugug", "gguggggggguuggguugggggg") == \
       "guguuuuuuuuuuuuuuguguggguggggggguuggguugggggg"  # Stress comparison case

assert solution.largestMerge("aaaaab", "aaaaaa") == "aaaaabaaaaaa"  # Prefix tie broken late
assert solution.largestMerge("b", "aaaa") == "baaaa"  # One dominant starting char

assert solution.largestMerge("abc", "def") == "defabc"  # Entire second string larger
assert solution.largestMerge("xyz", "abc") == "xyzabc"  # Entire first string larger

assert solution.largestMerge("a", "a") == "aa"  # Minimal equal case

Test	Why
"cabaa", "bcaaa"	Validates provided example
"abcabc", "abdcaba"	Tests multiple alternating choices
"a", "b"	Smallest valid unequal input
"abc", "abc"	Equal strings
"aaa", "aaa"	Long repeated equal prefixes
"abz", "abc"	Requires suffix comparison beyond first mismatch
"aaaaab", "aaaaaa"	Late lexicographical divergence
"b", "aaaa"	One string immediately dominates
"xyz", "abc"	Entire first string lexicographically larger
"a", "a"	Minimal equal input

Edge Cases

One important edge case occurs when the current leading characters are equal. A naive implementation might arbitrarily choose from one string, but that can produce a suboptimal answer. For example, with "abz" and "abc", both start with 'a', but "abz" is lexicographically larger because 'z' > 'c' later. The implementation correctly handles this by comparing the full remaining suffixes rather than only the current character.

Another tricky case occurs when one string is a prefix of the other. Consider "abc" and "abcde". The shorter string matches completely at the beginning, so the decision depends on which suffix continues longer and remains lexicographically larger. Python and Go string comparisons naturally handle this correctly because lexicographical ordering accounts for string length after matching prefixes.

Repeated characters can also create performance and correctness challenges. Inputs such as "aaaaaa" and "aaaaaa" force many deep suffix comparisons because large portions of the strings are identical. The algorithm still works correctly because it consistently compares the remaining suffixes. Although this increases runtime toward the quadratic worst case, it remains acceptable for the problem constraints.

A final important edge case occurs when one string becomes empty early. Once that happens, there is no longer any decision to make, and the remaining characters from the other string must be appended directly. The implementation handles this using the final append step after the main loop terminates.