Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1754. Largest Merge Of Two Strings - Leetcode Solution

Code Implementation

class Solution:
    def largestMerge(self, word1: str, word2: str) -> str:
        i, j = 0, 0
        merge = []
        while i < len(word1) and j < len(word2):
            if word1[i:] > word2[j:]:
                merge.append(word1[i])
                i += 1
            else:
                merge.append(word2[j])
                j += 1
        merge.append(word1[i:])
        merge.append(word2[j:])
        return ''.join(merge)
      
class Solution {
public:
    string largestMerge(string word1, string word2) {
        int i = 0, j = 0;
        string merge = "";
        int n1 = word1.size(), n2 = word2.size();
        while (i < n1 && j < n2) {
            if (word1.substr(i) > word2.substr(j)) {
                merge += word1[i++];
            } else {
                merge += word2[j++];
            }
        }
        merge += word1.substr(i);
        merge += word2.substr(j);
        return merge;
    }
};
      
class Solution {
    public String largestMerge(String word1, String word2) {
        int i = 0, j = 0;
        StringBuilder merge = new StringBuilder();
        while (i < word1.length() && j < word2.length()) {
            if (word1.substring(i).compareTo(word2.substring(j)) > 0) {
                merge.append(word1.charAt(i++));
            } else {
                merge.append(word2.charAt(j++));
            }
        }
        merge.append(word1.substring(i));
        merge.append(word2.substring(j));
        return merge.toString();
    }
}
      
var largestMerge = function(word1, word2) {
    let i = 0, j = 0;
    let merge = "";
    while (i < word1.length && j < word2.length) {
        if (word1.slice(i) > word2.slice(j)) {
            merge += word1[i++];
        } else {
            merge += word2[j++];
        }
    }
    merge += word1.slice(i);
    merge += word2.slice(j);
    return merge;
};

Problem Description

Given two strings, word1 and word2, you are to create a new string called the "largest merge" by merging the two input strings together. At each step, you choose either the first character of word1 or word2 to append to the result, then remove that character from its original string. You repeat this process until both strings are empty. The goal is to construct the lexicographically largest possible string (i.e., the string that would come last in dictionary order). Each character from each input string must be used exactly once, and you cannot reuse characters.

Thought Process

The naive approach is to try all possible ways of interleaving the two strings and pick the largest, but this is computationally infeasible for long strings due to the combinatorial explosion. Instead, we need a strategy to decide, at each step, which character to take so that the final string is as large as possible. The intuition is that, at each decision point, we should look ahead: if the remaining part of word1 is lexicographically larger than the remaining part of word2, then taking from word1 will help us make the merge as large as possible, and vice versa.

Solution Approach

To build the largest merge efficiently, we use a greedy algorithm:
  • We initialize two pointers, one for each word.
  • At each iteration, we compare the substrings starting at the current pointers of word1 and word2.
  • If word1's remaining substring is lexicographically greater, we take its first character and move its pointer forward.
  • Otherwise, we take the first character from word2 and move its pointer.
  • We continue this process until we've used all characters from both words.
  • Once one word is exhausted, we append the remainder of the other word to the result.
This approach ensures that at every step, we make the optimal local choice that leads to the globally largest possible merge. The reason this works is that the comparison of the remaining substrings accurately predicts which choice will lead to a better result, as lexicographical order is determined left-to-right.

Example Walkthrough

Let's consider word1 = "cabaa" and word2 = "bcaaa".
  • Step 1: Compare "cabaa" vs "bcaaa". "cabaa" > "bcaaa", so take 'c' from word1: merge = "c"
  • Step 2: Compare "abaa" vs "bcaaa". "bcaaa" > "abaa", so take 'b' from word2: merge = "cb"
  • Step 3: Compare "abaa" vs "caaa". "abaa" > "caaa" is false, so take 'c' from word2: merge = "cbc"
  • Step 4: Compare "abaa" vs "aaa". "abaa" > "aaa", so take 'a' from word1: merge = "cbca"
  • Step 5: Compare "baa" vs "aaa". "baa" > "aaa", so take 'b' from word1: merge = "cbcab"
  • Step 6: Compare "aa" vs "aaa". "aaa" > "aa", so take 'a' from word2: merge = "cbcaba"
  • Step 7: Compare "aa" vs "aa". Equal, so by convention, take from word2: merge = "cbcabaa"
  • Step 8: Compare "aa" vs "a". "aa" > "a", so take 'a' from word1: merge = "cbcabaaa"
  • Step 9: Compare "a" vs "a". Equal, so take from word2: merge = "cbcabaaaa"
  • Step 10: Only "a" left in word1, append it: merge = "cbcabaaaaa"
Final result: "cbcabaaaaa"

Time and Space Complexity

  • Brute-force approach: Trying all possible interleavings would have exponential time complexity, specifically O(2n+m), where n and m are the lengths of word1 and word2.
  • Optimized greedy approach: At each step, comparing the two substrings is O(k) where k is the remaining length, but in practice, the total number of comparisons is proportional to the total length, so the overall time complexity is O((n+m)2), since each substring comparison can take up to O(n+m) time and there are O(n+m) steps. (Some languages optimize substring comparison, so this is often fast enough for constraints.)
  • Space complexity: O(n+m) for the output string.

Summary

The largest merge problem is solved efficiently using a greedy algorithm that, at each step, compares the remaining substrings of the two input words and selects the optimal character. This approach ensures that the constructed string is lexicographically maximal. The solution is elegant because it leverages the properties of lexicographical order and avoids the combinatorial explosion of brute-force interleaving.