Scale Engineer

Largest Merge Of Two Strings

Med
#1606Time: O((N + M)^2). The main loop runs up to N + M times. In each iteration, if the characters are the same, we compare the suffixes. This comparison can take up to O(N + M) time in the worst case (e.g., for strings with long common prefixes). This results in a total time complexity that is quadratic in the sum of the string lengths.Space: O(N + M), where N and M are the lengths of `word1` and `word2`. This space is required for the `StringBuilder` that stores the merged string. In some language environments, creating substrings might add to the temporary space usage, but the overall auxiliary space complexity remains linear.1 company
Patterns
Two PointersGreedy
Data structures
String
Companies
Snap

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

A greedy strategy is well-suited for this problem. At each step of constructing the merge string, we should aim to append the largest possible character to ensure the final result is lexicographically maximal. If the current characters at the front of word1 and word2 are different, the choice is clear: we take the larger one. The critical part is handling ties, where the front characters are identical. In this scenario, our decision must be based on the characters that will follow. Therefore, we must compare the entire remaining suffixes of both strings. The string that provides a lexicographically larger suffix is the one we should take from. This greedy choice at each step guarantees the overall optimal solution.

Algorithm

  • Initialize two pointers, i for word1 and j for word2, starting at 0.
  • Create a StringBuilder to construct the merge string.
  • Loop as long as both i and j are within the bounds of their respective strings.
  • Inside the loop, compare word1.charAt(i) and word2.charAt(j):
    • If they are different, append the lexicographically larger character to merge and advance its corresponding pointer.
    • If they are the same, a tie-breaker is needed. Compare the entire remaining suffix of word1 (from index i) with the remaining suffix of word2 (from index j).
    • Append the character from the string with the lexicographically larger suffix and advance its pointer.
  • After the loop terminates, one of the strings may still have remaining characters. Append the rest of that string to merge.
  • Return the final merge string.

Walkthrough

This approach uses two pointers, i and j, to track the current position in word1 and word2, respectively. We iterate and build the result string character by character.

The core of the algorithm is the decision-making process inside the loop:

  1. If word1.charAt(i) is greater than word2.charAt(j), we append word1.charAt(i) to our result and increment i.
  2. If word2.charAt(j) is greater than word1.charAt(i), we append word2.charAt(j) and increment j.
  3. If word1.charAt(i) is equal to word2.charAt(j), we must resolve the tie by looking ahead. We perform a lexicographical comparison of the suffixes word1.substring(i) and word2.substring(j). If word1's suffix is larger, we take from word1; otherwise, we take from word2 (if word2's suffix is larger or they are equal, the choice leads to a better or equivalent result). The corresponding pointer is then incremented.

This continues until one string is fully consumed. Finally, we append the remainder of the other string to the result.

public String largestMerge(String word1, String word2) {    StringBuilder merge = new StringBuilder();    int i = 0, j = 0;    int n = word1.length(), m = word2.length();    while (i < n && j < m) {        if (word1.charAt(i) > word2.charAt(j)) {            merge.append(word1.charAt(i++));        } else if (word1.charAt(i) < word2.charAt(j)) {            merge.append(word2.charAt(j++));        } else {            // Tie-breaking by comparing the rest of the strings            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();}

Complexity

Time

O((N + M)^2). The main loop runs up to N + M times. In each iteration, if the characters are the same, we compare the suffixes. This comparison can take up to O(N + M) time in the worst case (e.g., for strings with long common prefixes). This results in a total time complexity that is quadratic in the sum of the string lengths.

Space

O(N + M), where N and M are the lengths of `word1` and `word2`. This space is required for the `StringBuilder` that stores the merged string. In some language environments, creating substrings might add to the temporary space usage, but the overall auxiliary space complexity remains linear.

Trade-offs

Pros

  • The logic is intuitive and directly follows the greedy principle.

  • It is relatively simple to implement using built-in string comparison functions.

Cons

  • The time complexity is quadratic, which might be too slow and could result in a 'Time Limit Exceeded' error on platforms with strict time limits, given the problem constraints.

Solutions

class Solution {public  String largestMerge(String word1, String word2) {    int m = word1.length(), n = word2.length();    int i = 0, j = 0;    StringBuilder ans = new StringBuilder();    while (i < m && j < n) {      boolean gt = word1.substring(i).compareTo(word2.substring(j)) > 0;      ans.append(gt ? word1.charAt(i++) : word2.charAt(j++));    }    ans.append(word1.substring(i));    ans.append(word2.substring(j));    return ans.toString();  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem