# Largest Merge Of Two Strings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-merge-of-two-strings)
Canonical: https://scaleengineer.com/dsa/problems/largest-merge-of-two-strings
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [Snap](https://scaleengineer.com/companies/snap)
---
## Problem
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
## Greedy with Suffix Comparison
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.
**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.
**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.
### Explanation
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.

```java
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();
}
```
### 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.

## Greedy with Suffix Array Optimization
The quadratic time complexity of the simple greedy approach is due to the expensive, repeated suffix comparisons within the main loop. This bottleneck can be addressed by using a more advanced data structure to speed up these comparisons. A Suffix Array is a perfect tool for this. By pre-processing the input strings and building a suffix array, we can determine the lexicographical order of any two suffixes in constant time. This optimization changes the complexity of the tie-breaking step from linear to constant, significantly improving the overall algorithm's efficiency.
**Time:** O((N+M) log(N+M)). The dominant part of the algorithm is the construction of the suffix array. The subsequent merging process is linear, O(N+M), as each step is O(1). · **Space:** O(N + M). This space is used for the combined string, the suffix array, the rank array, and the final merged string.
**Pros:** Highly efficient, with a time complexity of O((N+M) log(N+M)), which easily passes the given constraints.; It represents a standard and powerful technique for solving problems involving repeated suffix/substring comparisons.
**Cons:** The main drawback is implementation complexity. Constructing a suffix array efficiently is a non-trivial algorithm and is not typically expected in a standard coding interview unless string algorithms are a specific focus.
### Explanation
The core of this optimized approach is to replace the `O(N+M)` suffix comparison with an `O(1)` lookup. This is achieved through a one-time pre-computation step.

1.  **Preprocessing**: We form a single string `S = word1 + "#" + word2`, where `"#"` is a separator character smaller than 'a'. We then build a suffix array and a corresponding `rank` array for `S`. The `rank[k]` value gives us the lexicographical order of the suffix starting at index `k` of `S`. This preprocessing step typically takes `O((N+M) log(N+M))` time.

2.  **Merging**: We proceed with the same two-pointer greedy merge as before. However, when we encounter a tie (`word1.charAt(i) == word2.charAt(j)`), we use our pre-computed `rank` array. The suffix `word1[i:]` corresponds to the suffix of `S` starting at index `i`. The suffix `word2[j:]` corresponds to the suffix of `S` starting at index `n + 1 + j` (where `n` is the length of `word1`). We simply compare `rank[i]` and `rank[n + 1 + j]` to decide which suffix is larger. This check is now `O(1)`.

The merging loop still runs `N+M` times, but each step is now `O(1)`, making the merging process `O(N+M)`. The total time complexity is dominated by the initial suffix array construction.

```java
// The following code illustrates the merging logic assuming a pre-computed rank array.
// The implementation of buildRankArray is complex and omitted for brevity.

// public int[] buildRankArray(String word1, String word2) { ... }

public String largestMerge(String word1, String word2) {
    // In a real implementation, you would call a function to build the rank array.
    // int[] rank = buildRankArray(word1, word2);
    // For this example, we'll use the slower comparison to keep the code runnable,
    // but conceptually, this is where the O(1) lookup would happen.

    StringBuilder merge = new StringBuilder();
    int i = 0, j = 0;
    int n = word1.length(), m = word2.length();

    while (i < n && j < m) {
        // The O(1) check would be: if (rank[i] > rank[n + 1 + j])
        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();
}
```
### Algorithm
- Combine `word1` and `word2` into a single string `S`, separated by a special character (e.g., `S = word1 + '#' + word2`). The separator must be lexicographically smaller than any character in the words.
- Construct a Suffix Array for `S`. This involves creating an array of all suffix starting positions, sorted lexicographically.
- From the Suffix Array, compute a `rank` array, where `rank[k]` stores the lexicographical rank of the suffix starting at `S[k]`.
- Use the same greedy merging logic as the previous approach with two pointers, `i` and `j`.
- When a tie occurs (`word1.charAt(i) == word2.charAt(j)`), use the `rank` array for an O(1) comparison. Compare `rank[i]` (for `word1`'s suffix) with `rank[n + 1 + j]` (for `word2`'s suffix) to decide which is larger.
- Append the chosen character and advance the corresponding pointer.
- After the loop, append any remaining parts of the strings.

# Solutions
### Java

```java
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();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string largestMerge(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    int i = 0, j = 0;
    string ans;
    while (i < m && j < n) {
      bool gt = word1.substr(i) > word2.substr(j);
      ans += gt ? word1[i++] : word2[j++];
    }
    ans += word1.substr(i);
    ans += word2.substr(j);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def largestMerge(self, word1: str, word2: str) -> str: i = j = 0 ans = [] while i < len(word1) and j < len(word2): if word1[i:] > word2[j:]: ans . append(word1[i]) i += 1 else: ans . append(word2[j]) j += 1 ans . append(word1[i:]) ans . append(word2[j:]) return "" . join(ans)

```