Largest Merge Of Two Strings — LeetCode 1754 Python Solution

The 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.

Example

Input

word1 = "cabaa", word2 = "bcaaa"

Output

"cbcabaaaaa"

Explanation

One way to get the lexicographically largest merge is:

Python solution

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)

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 1754. Largest Merge Of Two Strings is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems