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 lexicographicallylargest _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.

Examples

Example 1

1
2
3
4
5
6
7
8
9

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

1
2

Input: word1 = "abcabc", word2 = "abdcaba"
Output: "abdcabcabcaba"

Constraints

  • 1 <= word1.length, word2.length <= 3000
  • word1 and word2 consist only of lowercase English letters.

Solution

Method 1 – Greedy Lexicographical Merge

Intuition

To get the lexicographically largest merge, always pick the first character from the string whose remaining suffix is lexicographically larger. This ensures the merge is as large as possible at every step.

Approach

  1. Use two pointers for word1 and word2.
  2. At each step, compare the remaining substrings word1[i:] and word2[j:].
  3. If word1[i:] > word2[j:], append word1[i] to the result and increment i.
  4. Otherwise, append word2[j] to the result and increment j.
  5. Continue until both strings are exhausted.
  6. Return the merged string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    string largestMerge(string word1, string word2) {
        int i = 0, j = 0, n = word1.size(), m = word2.size();
        string ans;
        while (i < n || j < m) {
            if (word1.substr(i) > word2.substr(j)) ans += word1[i++];
            else ans += word2[j++];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func largestMerge(word1, word2 string) string {
    i, j := 0, 0
    n, m := len(word1), len(word2)
    ans := make([]byte, 0, n+m)
    for i < n || j < m {
        if word1[i:] > word2[j:] {
            ans = append(ans, word1[i])
            i++
        } else {
            ans = append(ans, word2[j])
            j++
        }
    }
    return string(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public String largestMerge(String word1, String word2) {
        int i = 0, j = 0, n = word1.length(), m = word2.length();
        StringBuilder ans = new StringBuilder();
        while (i < n || j < m) {
            if (word1.substring(i).compareTo(word2.substring(j)) > 0) ans.append(word1.charAt(i++));
            else ans.append(word2.charAt(j++));
        }
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun largestMerge(word1: String, word2: String): String {
        var i = 0; var j = 0
        val n = word1.length; val m = word2.length
        val ans = StringBuilder()
        while (i < n || j < m) {
            if (word1.substring(i) > word2.substring(j)) ans.append(word1[i++])
            else ans.append(word2[j++])
        }
        return ans.toString()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def largestMerge(self, word1: str, word2: str) -> str:
        i, j = 0, 0
        n, m = len(word1), len(word2)
        ans = []
        while i < n or j < m:
            if word1[i:] > word2[j:]:
                ans.append(word1[i])
                i += 1
            else:
                ans.append(word2[j])
                j += 1
        return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn largest_merge(word1: String, word2: String) -> String {
        let (mut i, mut j) = (0, 0);
        let n = word1.len();
        let m = word2.len();
        let w1 = word1.as_bytes();
        let w2 = word2.as_bytes();
        let mut ans = Vec::with_capacity(n + m);
        while i < n || j < m {
            if &w1[i..] > &w2[j..] {
                ans.push(w1[i]);
                i += 1;
            } else {
                ans.push(w2[j]);
                j += 1;
            }
        }
        String::from_utf8(ans).unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    largestMerge(word1: string, word2: string): string {
        let i = 0, j = 0, n = word1.length, m = word2.length;
        let ans = '';
        while (i < n || j < m) {
            if (word1.slice(i) > word2.slice(j)) ans += word1[i++];
            else ans += word2[j++];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O((n+m)^2), where n and m are the lengths of word1 and word2. Each comparison of suffixes can take O(n+m) time.
  • 🧺 Space complexity: O(n+m), for the result string.