#1754

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Largest Merge Of Two Strings

Construct the lexicographically largest merge from two strings using a two-pointer greedy scanning approach efficiently.

two pointers string greedy

Problem Statement

Given two strings word1 and word2, you need to create a new string merge by repeatedly choosing either the first character of word1 or word2 until both strings are empty. Each choice should aim to make merge lexicographically as large as possible.

Return the resulting lexicographically largest merge. A string a is larger than string b if at the first differing character a has a higher letter than b. For example, 'abcd' is larger than 'abcc' because 'd' > 'c' at the fourth position.

Examples

Example 1

Input: word1 = "cabaa", word2 = "bcaaa"

Output: "cbcabaaaaa"

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"

Example details omitted.

Constraints

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

Solution Approach

Two-Pointer Greedy Scanning

Use two pointers starting at the beginning of word1 and word2. At each step, compare the current substrings starting from the pointers. Append the character from the string whose substring is lexicographically larger. Move that pointer forward and repeat until both strings are consumed.

Efficient Substring Comparison

Instead of comparing full remaining strings each time, consider using simple string slicing or built-in comparison operators to efficiently decide which character to pick. This preserves the invariant that merge remains lexicographically maximal at each choice.

Edge Case Handling

Handle cases where one string becomes empty before the other. In such scenarios, append all remaining characters from the non-empty string to merge. This ensures correctness without breaking the greedy invariant.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m) if comparisons of remaining substrings are optimized, where n and m are the lengths of word1 and word2. Space complexity is O(n + m) for storing the merged string.

What Interviewers Usually Probe

Looking for two-pointer and greedy understanding.
Expect efficient lexicographical comparison without redundant scanning.
Check for correct handling when one string is exhausted before the other.

Common Pitfalls or Variants

Common pitfalls

Naively concatenating characters without checking remaining substrings can fail on ties.
Comparing only the first characters instead of full remaining substrings may produce a smaller merge.
Forgetting to append the leftover of the non-empty string after the other is exhausted.

Follow-up variants

Return the lexicographically smallest merge instead of largest.
Merge more than two strings simultaneously using a generalized two-pointer greedy approach.
Apply the same merge logic with uppercase letters or custom lexicographical orders.

FAQ

What is the main strategy for Largest Merge Of Two Strings?

The main strategy is two-pointer greedy scanning, choosing the lexicographically larger remaining substring at each step.

How do I handle ties between the first characters of word1 and word2?

Compare the remaining substrings starting from the tie point and choose the one that is lexicographically larger.

Can this approach work efficiently for long strings?

Yes, with optimized substring comparisons or slicing, the two-pointer method achieves linear time relative to total string length.

What if one string runs out before the other?

Simply append all remaining characters from the non-empty string to the merge; this maintains the maximal lexicographical result.

Does this solution pattern appear in other string problems?

Yes, two-pointer scanning with greedy invariant tracking is common in string merging and lexicographical optimization problems.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

Continue Practicing

#1850 minimum adjacent swaps to reach the kth smallest number #1963 minimum number of swaps to make the string balanced #2193 minimum number of moves to make palindrome