Greatest Interleave of Two Words

Medium

You are given two strings left and right of lowercase English letters. Build a new string: while at least one of them is non-empty, remove the first letter of left or of right (either non-empty one) and append it to the result. Every letter ends up used exactly once, and the order of letters within each original string is preserved. Return the lexicographically largest result you can build this way.

Example 1

left="bad", right="cab" → 'cbadab'

Take c from right, then b from left (the remainder bad beats ab). Since ad beats ab, the next two letters a and d come from left, and ab closes the string: cbadab.

Example 2

left="zz", right="y" → 'zzy'

Both z letters are best placed at the front.

Example 3

left="aab", right="aac" → 'aacaab'

Constraints

1 ≤ len(left), len(right) ≤ 3000
Both strings consist of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Two Pointers String

Similar problems

Pieces Without Shared Letters Medium A Note From Headline Cutouts Medium Swaps to the k-th Next Arrangement Medium Swapping Brackets Into Balance Medium Finish the Word by Appending Medium

Input

left="bad", right="cab"

Expected

'cbadab'

Run checks the first 3 tests in your browser. Submit checks all 139 tests on the server, hidden ones included.