0660EasyArrayHash TableString

Tiles Every Rack Can Supply

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Each player in a word game holds a rack of letter tiles. racks[i] is a string listing the tiles on the i-th rack, one lowercase letter per tile.

The umpire wants the multiset of tiles that every rack can supply at the same time. Copies count: if a letter is on one rack three times and on another rack twice, then only two copies of it can come from every rack.

Return those tiles as a list of one-letter strings, one entry per copy. Any order is accepted. Return an empty list when no letter sits on every rack.

Examples

Example 1

Input: racks = ["ppqqr", "pqrst", "zpqq"]
Output: ["p", "q"]

Letter p sits on all three racks once each, so one copy is available. Letter q sits twice, once and twice, so one copy is available. Letter r is missing from the third rack, and no other letter is on all three.

Example 2

Input: racks = ["eexz", "zex"]
Output: ["e", "x", "z"]

The first rack has two e tiles but the second has only one, so one e can come from both. Letters x and z are on each rack once.

Example 3

Input: racks = ["hjk", "wxy"]
Output: []

The two racks share no letter at all, so the answer is the empty list.

Constraints

1 <= racks.length <= 100
1 <= racks[i].length <= 100
racks[i] consists of lowercase English letters.

The values you return may be in any order.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def shared_tiles(racks: list[str]) -> list[str]:

Java

public List<String> sharedTiles(String[] racks)

The intended approach

Time O(L + 26 * m) where L is the total number of tiles and m the number of racks.Space O(1) beyond the returned list: two fixed arrays of 26 counters.

Count the 26 letters separately for each rack and keep, for every letter, the smallest count any rack showed. That smallest count is exactly how many copies every rack can supply at once. Walk the 26 letters at the end and emit each one as many times as its stored minimum.

Pythonentry point: shared_tiles

def shared_tiles(racks):
    # For each letter, the number of copies every rack can supply is the smallest
    # count across the racks. O(total letters) time, O(1) extra space (26 slots).
    letters = "abcdefghijklmnopqrstuvwxyz"
    floor = [None] * 26
    for rack in racks:
        seen = [0] * 26
        for ch in rack:
            seen[ord(ch) - 97] += 1
        for i in range(26):
            if floor[i] is None or seen[i] < floor[i]:
                floor[i] = seen[i]
    out = []
    for i in range(26):
        for _ in range(floor[i]):
            out.append(letters[i])
    return out

The obvious version

Start with the first rack's tiles as the running pool. For each later rack, take a spare copy of it and try to match every tile in the pool against a distinct tile of the spare copy, removing what it matches, then keep only the matched tiles as the new pool.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_shared_tiles(racks):
    pool = list(racks[0])
    for rack in racks[1:]:
        spare = list(rack)
        kept = []
        for ch in pool:
            if ch in spare:
                spare.remove(ch)
                kept.append(ch)
        pool = kept
    return pool

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in