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.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.
C++
Java
C#
JavaScript
C
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.
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,200 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