Loading page…
Practice problem · medium
A chat app has a sticker maker. Users get a pool of letter tiles, and they can spell a word as a sticker when the pool holds enough tiles of each letter.
You get a list of words that users want to spell and the pool of tiles. Each word is checked on its own against the full pool, so tiles are not used up by other words. You count the words that can be spelled.
Write count_buildable_words(words, pool).
words[i] is a word a user wants to spell. pool holds the available tiles, one letter per tile.Input: words = ["tea", "tee", "ate"], pool = "tea"
Output: 2The trace counts the tiles of the pool, then checks each word. The pool tea has t: 1, e: 1, a: 1.
| Word | Letters needed | Pool has enough? | Count so far |
|---|---|---|---|
| tea | t: 1, e: 1, a: 1 | yes | 1 |
| tee | t: 1, e: 2 | no: only one e | 1 |
| ate | a: 1, t: 1, e: 1 | yes | 2 |
Two words can be spelled, so the output is 2.
Input: words = [], pool = "abc"
Output: 0With no words, there is nothing to count.
Input: words = ["aa"], pool = "a"
Output: 0The word aa needs two a tiles, but the pool has one, so the output is 0.
0 ≤ words.length ≤ 100,000 (requested words)1 ≤ words[i].length ≤ 200 ≤ pool.length ≤ 100,000 (tiles)a to z.For each word, removing its letters from a copy of the pool one by one costs the pool length per letter, which can reach 100,000 × 20 per word. Counting the pool once costs P steps, and each word then costs at most 20 steps. The total is about 100,000 + 2,000,000 steps.
count_buildable_words · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.