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:
word1 is non-empty, append the first character in word1 to merge and delete it from word1.
word1 = "abc" and merge = "dv", then after choosing this operation, word1 = "bc" and merge = "dva".word2 is non-empty, append the first character in word2 to merge and delete it from word2.
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 <= 3000word1 and word2 consist only of lowercase English letters.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.
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.
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.
| Approach | Complexity |
|---|---|
| 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. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Backtracking | O(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 case | O(1) | General optimal approach used in interviews and production solutions |
Leetcode 1754. Largest Merge Of Two Strings • Fraz • 1,068 views views
Watch 9 more video solutions →Practice Largest Merge Of Two Strings with our built-in code editor and test cases.
Practice on FleetCode