0498EasyHash TableStringCounting

Kettle Signs from the Tile Tray

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.

A sign shop keeps loose letter tiles in one tray. The string tiles gives the letter printed on each tile in the tray, one lowercase letter per tile.

A finished sign spells the word kettle, so laying out one sign takes a k tile, two e tiles, two t tiles and an l tile. A tile can only be laid into one sign: once it is used it is gone for the rest of the run, and tiles printed with any other letter are no help at all.

Return how many finished signs the shop can lay out from the tray it has.

Examples

Example 1

Input: tiles = "ttlleekkeettll"
Output: 2

The tray holds two k tiles, four e tiles, four t tiles and four l tiles. Two signs use two k, four e, four t and two l tiles, which the tray covers, and two l tiles are left over.

Example 2

Input: tiles = "kkeeeetttlll"
Output: 1

One sign takes a k, two e, two t and an l tile. That leaves a k, two e, a t and two l tiles sitting unused in the tray.

Example 3

Input: tiles = "settlement"
Output: 0

There is no k tile anywhere in the tray, so no sign can be laid out.

Constraints

1 <= tiles.length <= 10^4
tiles consists of lowercase English letters only

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 kettle_signs(tiles: str) -> int:

Java

public int kettleSigns(String tiles)

The intended approach

Time O(n) for a tray of n tiles: one walk, then four lookups.Space O(1): the tally holds at most 26 letters whatever the tray size.

Walk the tray once and tally how many tiles carry each letter. A sign needs one `k` and one `l`, so those tallies cap the run directly, while `e` and `t` go two to a sign, so halve those tallies and drop the remainder. The smallest of the four caps is the answer, since every sign has to satisfy all four at once.

Pythonentry point: kettle_signs

def kettle_signs(tiles):
    # one walk of the tray fills a tally that holds at most 26 letters
    tally = {}
    for letter in tiles:
        tally[letter] = tally.get(letter, 0) + 1
    return min(tally.get("k", 0),
               tally.get("e", 0) // 2,
               tally.get("t", 0) // 2,
               tally.get("l", 0))

The obvious version

Lay out signs one at a time. For each attempt take a copy of the remaining tiles and pull out the six letters a sign needs one by one; if any of them is missing, report how many signs were finished before this attempt.

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_kettle_signs(tiles):
    pool = list(tiles)
    wanted = ["k", "e", "t", "t", "l", "e"]
    built = 0
    while True:
        attempt = list(pool)
        for letter in wanted:
            if letter in attempt:
                attempt.remove(letter)
            else:
                return built
        pool = attempt
        built += 1

How this problem was checked

Reference solution executed against 11 test cases — 11 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