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.

Solution

Method 1 – Greedy Lexicographical Merge

Intuition

To get the lexicographically largest merge, always pick the first character from the string whose remaining suffix is lexicographically larger. This ensures the merge is as large as possible at every step.

Approach

Use two pointers for word1 and word2.
At each step, compare the remaining substrings word1[i:] and word2[j:].
If word1[i:] > word2[j:], append word1[i] to the result and increment i.
Otherwise, append word2[j] to the result and increment j.
Continue until both strings are exhausted.
Return the merged string.

Code

Related Tags