Watch 10 video solutions for Largest Merge Of Two Strings, a medium level problem involving Two Pointers, String, Greedy. This walkthrough by Fraz has 1,068 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |