0759HardArrayMathStringBinary SearchDynamic Programming

Labels Printable With The Stamps On Hand

Tracked in this browser only

Trains the technique from

LeetCode 902Numbers At Most N Given Digit Set

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 hand press builds a label by pressing digit stamps left to right, and the finished label is read as an ordinary decimal number. The tray holds the stamps listed in stamps, each a one-character string. A stamp can be pressed as many times as you like, and a label may be any length from one stamp upwards.

Return how many different positive integers no greater than limit can be produced this way. Two labels that read as the same number count once. Since no stamp carries the digit 0, a number needing a 0 anywhere cannot be pressed at all.

Examples

Example 1

Input: stamps = ["2", "4", "7"], limit = 386
Output: 21

The one-stamp labels 2, 4 and 7 all fit, and so do the nine two-stamp labels from 22 up to 77. Of the three-stamp labels only 222, 224, 227, 242, 244, 247, 272, 274 and 277 come out at 386 or below, giving twenty-one labels in all.

Example 2

Input: stamps = ["1", "5"], limit = 15
Output: 4

The printable values at 15 or below are 1, 5, 11 and 15. The remaining two-stamp labels, 51 and 55, are both over the limit.

Example 3

Input: stamps = ["5"], limit = 4
Output: 0

The shortest label the tray can press reads 5, which is already above the limit, so no value qualifies.

Constraints

1 <= stamps.length <= 9
stamps[i].length == 1
Each entry of stamps is one of the characters '1' through '9'.
The entries of stamps are distinct and listed in increasing order.
1 <= limit <= 10^9

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 printable_labels(stamps: list[str], limit: int) -> int:

Java

public int printableLabels(String[] stamps, int limit)

The intended approach

Time O(D * L) for D stamps and a limit with L digits.Space O(D) for the stamp lookup.

Split the count by label length. Any label strictly shorter than the digit count of `limit` is automatically small enough, and with `k` stamps there are `k ** size` labels of each such size. For labels of exactly the same length, walk `limit` from its leading digit: at each position, choosing any stamp strictly below that digit leaves every later position free, which adds `smaller * k ** remaining`. Continue only while the current digit is itself a stamp, since otherwise no label can match the prefix; if the walk survives every position, `limit` itself is printable and adds one more.

Pythonentry point: printable_labels

def printable_labels(stamps, limit):
    # Count by label length. Every length below the digit count of `limit` is free,
    # then walk `limit` position by position, holding the prefix pressed exactly.
    # Time O(D * L) for D stamps and an L digit limit, space O(D).
    text = str(limit)
    length = len(text)
    k = len(stamps)
    total = 0
    for size in range(1, length):
        total += k ** size
    available = set(stamps)
    for i, ch in enumerate(text):
        smaller = 0
        for d in stamps:
            if d < ch:
                smaller += 1
        total += smaller * (k ** (length - i - 1))
        if ch not in available:
            break
    else:
        total += 1
    return total

The obvious version

Try every integer from 1 up to the limit and keep the ones whose decimal digits are all on the tray. Linear in the limit, so only usable when the limit is small.

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_printable_labels(stamps, limit):
    available = set(stamps)
    total = 0
    for v in range(1, limit + 1):
        ok = True
        for ch in str(v):
            if ch not in available:
                ok = False
                break
        if ok:
            total += 1
    return total

How this problem was checked

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