Skip to main content
Talentd

Largest Merge Of Two Strings - Solution & Explanation

MediumTwo PointersStringGreedy10 min readAsked at: Snapchat
Practice this problem

Problem Statement

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.

 

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"

 

Constraints:

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

Approach Overview

Problem Overview: You are given two strings word1 and word2. At each step you can take the first character from either string and append it to a result. The goal is to build the lexicographically largest possible merged string while preserving the relative order of characters within each original string.

Approach 1: Brute Force Backtracking (Exponential Time, O(2^(n+m)) time, O(n+m) space)

The naive idea tries every possible merge. At each step, you either pick the next character from word1 or from word2, then recursively continue building the merge. After generating all possible valid merges, return the lexicographically largest result. This approach quickly becomes infeasible because the number of possible merges grows exponentially with the string lengths. It mainly serves as a conceptual baseline that clarifies the search space.

Approach 2: Lexicographical Comparison with Greedy Selection (Two Pointers + Greedy) (O((n+m)^2) worst-case time, O(1) space)

The key observation: when choosing the next character, the locally optimal decision depends on the remaining suffix of each string. If the remaining substring of word1 is lexicographically larger than the remaining substring of word2, you should take the next character from word1. Otherwise, take it from word2. This guarantees the final merge stays as large as possible.

Use two pointers i and j to track positions in the two strings. At each step compare word1[i:] and word2[j:]. Append the first character from the larger suffix and move the corresponding pointer forward. Continue until both strings are exhausted. The comparison step may scan multiple characters, giving a worst-case complexity of O((n+m)^2), though it performs close to linear in typical cases.

This approach combines greedy decision making with two pointers on string suffixes. Instead of exploring all merges, it always commits to the choice that keeps the remaining result lexicographically maximal.

Recommended for interviews: The greedy suffix comparison approach is what interviewers expect. The brute force idea demonstrates understanding of the merge possibilities, but recognizing that comparing the remaining suffixes lets you make a greedy decision shows algorithmic maturity. Implementing the two‑pointer greedy solution clearly and handling equal prefixes correctly is the key skill tested in this problem.

Approach 1: Lexicographical Comparison with Greedy Selection

The main objective is to construct a merge string that is lexicographically largest. To achieve this, we can utilize a greedy strategy. At each step, we compare the current prefixes of word1 and word2. We append the character from the beginning of the string that is larger when considering the remaining portion of each string. If word1 and word2 have the same starting character, compare the substrings starting from the second character to decide which path would lead to a greater lexicographical order.

This solution utilizes a greedy approach to construct the largest merge string. We maintain indices i and j to iterate through word1 and word2. At each step, we compare the suffixes starting at the current indices to decide which character to add to the merge. The algorithm continues until one of the strings is exhausted, at which point the remainder of the other string is appended to the merge.

Code

PythonC++JavaC#JavaScriptC

Python

C++

Java

C#

JavaScript

C

Complexity

Time Complexity: O(n + m), where n and m are the lengths of word1 and word2, respectively. This is because each character from both strings is processed exactly once.
Space Complexity: O(n + m), for storing the resulting merge.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Lexicographical Comparison with Greedy Selection

Time Complexity: O(n + m), where n and m are the lengths of word1 and word2, respectively. This is because each character from both strings is processed exactly once.
Space Complexity: O(n + m), for storing the resulting merge.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force BacktrackingO(2^(n+m))O(n+m)Conceptual baseline to understand all valid merges; not practical for large inputs
Greedy Lexicographical Comparison (Two Pointers)O((n+m)^2) worst caseO(1)General optimal approach used in interviews and production solutions

Video Solution

Leetcode 1754. Largest Merge Of Two Strings • Fraz • 1,135 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Largest Merge Of Two Strings easy or hard?
Largest Merge Of Two Strings is rated Medium difficulty. The implementation is straightforward once you realize that comparing the remaining suffixes allows a greedy choice, but identifying this insight can take time during interviews.
Largest Merge Of Two Strings Python/Java solution
In Python or Java, implement two indices pointing to the current position in each string. Compare the remaining substrings and append the next character from the larger one. Continue until both strings are fully consumed to build the final merge.
How to solve Largest Merge Of Two Strings in O(n)?
Use two pointers and always compare the remaining suffixes of the two strings. If word1[i:] is greater than word2[j:], append word1[i]; otherwise append word2[j]. Each step consumes one character, so the main loop runs n+m iterations, though substring comparisons can add overhead depending on implementation.
What is the best approach for Largest Merge Of Two Strings?
The best approach uses a greedy strategy with two pointers. At each step compare the remaining substrings of word1 and word2 and append the first character from the lexicographically larger suffix. This guarantees the final merged string stays as large as possible while preserving order within each string.
Is Largest Merge Of Two Strings asked at Google/Amazon/Meta?
Greedy string comparison problems similar to Largest Merge Of Two Strings appear in interviews at companies like Amazon, Google, and Meta. Interviewers often use variations that test lexicographical ordering, greedy decisions, and two‑pointer string processing.
What data structure is used in Largest Merge Of Two Strings?
The problem mainly relies on string operations and a two‑pointer technique. No complex data structures are required; the algorithm repeatedly compares string suffixes and appends characters to a result string.
What is the time complexity of Largest Merge Of Two Strings?
The standard greedy solution runs in O((n+m)^2) time in the worst case because comparing the remaining suffixes may scan multiple characters repeatedly. Space complexity is O(1) since the algorithm only maintains two indices and builds the output string.

Ready to solve this problem?

Practice Largest Merge Of Two Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Decremental String Concatenation

Next

Maximum Matching of Players With Trainers