Show problems as
Classic problem #1160EasyArrayHash TableStringCounting

Find Words That Can Be Formed by Characters

Real-world version: Signs Spellable From A Tile Tray
Tracked in this browser only
Read Find Words That Can Be Formed by Characters on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A sign shop keeps one tray of loose letter tiles, given as the string tray: each character of tray is one physical tile, so a letter appearing three times in tray means the shop owns three tiles of it.

A sign whose text is label can be cut when the tray holds enough tiles to spell it: every letter of label needs its own tile, so a label using a letter twice needs two tiles of that letter. Deciding whether one label can be cut never uses up the tray — each label in labels is judged against the full tray, and the same label may appear in labels more than once, in which case it counts each time.

Return the total number of tiles the shop would place across all the labels it can cut, which is the sum of the lengths of those labels.

Examples

Example 1

Input
labels = ["glow", "gong", "log", "wool"], tray = "gowlno"
Output
11

The tray stocks one `g`, two `o`, one `w`, one `l` and one `n`. `"glow"` uses four tiles and `"log"` uses three, and `"wool"` uses four including both `o` tiles, so those three labels contribute 4 + 3 + 4. `"gong"` needs two `g` tiles and the tray has one.

Example 2

Input
labels = ["pepper", "per"], tray = "prepe"
Output
3

The tray stocks two `p`, one `r` and two `e`. `"pepper"` needs three `p` tiles, which the tray cannot supply. `"per"` needs one of each and contributes its three tiles.

Example 3

Input
labels = ["zz"], tray = "z"
Output
0

The label wants two `z` tiles and the tray holds one, so no label can be cut and no tiles are placed.

Constraints

  • 1 <= labels.length <= 1000
  • 1 <= labels[i].length, tray.length <= 100
  • labels[i] and tray consist of lowercase English letters only.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def total_spellable_length(labels: list[str], tray: str) -> int:
Java
public int totalSpellableLength(String[] labels, String tray)

More on the same topics