Words Holding Every Sample

Medium

You get two lists of strings, words and samples. Say a word w holds a sample s if every letter of s appears in w at least as many times as it does in s (the order of letters does not matter). For example, "ell" fits inside "hello" but not inside "help". Return every word in words that holds each sample in samples. The words may be returned in any order.

Example 1

words=["banana", "cabin", "nab", "bandana"], samples=["ban", "aa"] → ['banana', 'bandana']

A word needs b, n and two as. banana and bandana have them; cabin and nab have only one a.

Example 2

words=["stone", "notes", "tones"], samples=["net", "so"] → ['stone', 'notes', 'tones']

All three words are rearrangements of the same letters, and each contains n, e, t, s, o.

Example 3

words=["loop", "pool"], samples=["ooo"] → []

Constraints

1 ≤ len(words), len(samples) ≤ 10⁴
1 ≤ len(words[i]), len(samples[i]) ≤ 10
All strings consist of lowercase English letters
The strings in words are pairwise distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String

Similar problems

Anagram Buckets Medium Split Into Dictionary Words Medium Words Equal Up to a Shift Medium A Subsequence of One Word Only Medium Files With the Same Content Medium

Input

words=["banana", "cabin", "nab", "bandana"], samples=["ban", "aa"]

Expected

['banana', 'bandana']

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