1754. Largest Merge Of Two Strings LeetCode Solution

In this guide, you will get 1754. Largest Merge Of Two Strings LeetCode Solution with the best time and space complexity. The solution to Largest Merge Of Two Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Largest Merge Of Two Strings solution in C++
Largest Merge Of Two Strings solution in Java
Largest Merge Of Two Strings solution in Python
Additional Resources

1754. Largest Merge Of Two Strings LeetCode Solution image

Problem Statement of 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 word1 is non-empty, append the first character in word1 to merge and delete it from word1.

For example, if word1 = “abc” and merge = “dv”, then after choosing this operation, word1 = “bc” and merge = “dva”.

If word2 is non-empty, append the first character in word2 to merge and delete it from word2.

For example, if 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 <= 3000
word1 and word2 consist only of lowercase English letters.

Complexity Analysis

Time Complexity: O(|\texttt{word1}|^2 + |\texttt{word2}|^2)
Space Complexity: O(|\texttt{word1}|^2 + |\texttt{word2}|^2)

1754. Largest Merge Of Two Strings LeetCode Solution in C++

class Solution {
 public:
  string largestMerge(string word1, string word2) {
    if (word1.empty())
      return word2;
    if (word2.empty())
      return word1;
    return word1 > word2 ? word1[0] + largestMerge(word1.substr(1), word2)
                         : word2[0] + largestMerge(word1, word2.substr(1));
  }
};
/* code provided by PROGIEZ */

1754. Largest Merge Of Two Strings LeetCode Solution in Java

class Solution {
  public String largestMerge(String word1, String word2) {
    if (word1.isEmpty())
      return word2;
    if (word2.isEmpty())
      return word1;
    return word1.compareTo(word2) > 0 ? word1.charAt(0) + largestMerge(word1.substring(1), word2)
                                      : word2.charAt(0) + largestMerge(word1, word2.substring(1));
  }
}
// code provided by PROGIEZ

1754. Largest Merge Of Two Strings LeetCode Solution in Python

class Solution:
  def largestMerge(self, word1: str, word2: str) -> str:
    if not word1:
      return word2
    if not word2:
      return word1
    if word1 > word2:
      return word1[0] + self.largestMerge(word1[1:], word2)
    return word2[0] + self.largestMerge(word1, word2[1:])
 # code by PROGIEZ