151. Longest Word by Erasing
A word game gives you a string s and a list of candidate words. You may erase any letters of s you like, but you cannot reorder the rest. A candidate is playable if it is what remains after some erasures.
The candidate list is passed as one string dictionary in which words are separated by spaces; ignore any empty pieces caused by extra spaces. Return the playable word with the greatest length. If several playable words share that length, return the lexicographically smallest one. If no word is playable, return the empty string.
Example 1
- Input:
- s = "sunflowers"dictionary = "sun flow lower swore flows unfold sunny"
- Output:
- "flows"
- Explanation:
Playable words: sun, flow, lower, flows. The longest length is 5, shared by lower and flows. flows is lexicographically smaller, so it is returned.
Example 2
- Input:
- s = "abc", dictionary = "xyz qq"
- Output:
- ""
- Explanation:
Neither xyz nor qq can be formed from abc, so the answer is the empty string.
Example 3
- Input:
- s = "aabbcc", dictionary = "abc cba aabb bbcc ab"
- Output:
- "aabb"
- Explanation:
The playable words are abc, aabb, bbcc and ab. aabb and bbcc both have length 4, and aabb comes first alphabetically.
Constraints
1 ≤ s.length ≤ 105
1 ≤ dictionary.length ≤ 105
s consists of lowercase letters. dictionary consists of lowercase letters and spaces.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O((n + L) log n)
- Space
- O(n)