Largest Merge Of Two Strings
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
word1is non-empty, append the first character inword1tomergeand delete it fromword1. - If
word2is non-empty, append the first character inword2tomergeand delete it fromword2.
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.
Example 1
Input
word1 = "cabaa", word2 = "bcaaa"Output
"cbcabaaaaa"One way to get the lexicographically largest merge is to take characters producing "cbcaba" first, then append the remaining five 'a' characters from both strings.
Example 2
Input
word1 = "abcabc", word2 = "abdcaba"Output
"abdcabcabcaba"Choosing from the string whose remaining suffix is lexicographically larger at each step produces the largest possible merge.
Constraints
- 1 <= word1.length, word2.length <= 3000
- word1 and word2 consist only of lowercase English letters.