Longest Word by Crossing Out

Medium

You are given a string text and a list of words words. You may cross out any letters of text; the remaining letters are read in their original order. Find the longest word in words that can be obtained from text this way. If several fitting words share the maximum length, return the alphabetically smallest one. If no word fits, return the empty string.

Example 1

text='planetarium', words=['plum', 'planet', 'train', 'pear'] → 'planet'

Crossing letters out of planetarium gives plum, planet and pear; train is impossible, since no a follows the r. The longest is planet.

Example 2

text='bread', words=['bed', 'red', 'bad'] → 'bad'

All three words of length 3 fit, and bad comes first alphabetically.

Example 3

text='abc', words=['cab', 'd'] → ''

Letters cannot be reordered, so cab is out, and there is no d in the text. The answer is the empty string.

Constraints

0 ≤ len(text) ≤ 1000
1 ≤ len(words) ≤ 1000
0 ≤ len(words[i]) ≤ 1000
text and words[i] consist of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers String Sorting

Similar problems

A Subsequence of One Word Only Medium Word Growth Chain Medium Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium

Input

text='planetarium', words=['plum', 'planet', 'train', 'pear']

Expected

'planet'

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