0882EasyArrayHash TableStringBit ManipulationCounting

Labels the Press Can Set

Tracked in this browser only

Trains the technique from

LeetCode 1684Count the Number of Consistent Strings

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 holds type for the distinct letters listed in allowed, and it can set a label only if every letter of that label is among them. A letter may be used as often as needed.

Given the labels in words, return how many of them the press can set.

Examples

Example 1

Input: allowed = "fedcba", words = ["cafe", "faced", "deface", "bagged", "zebra"]
Output: 3

The press holds the first six letters. "cafe", "faced" and "deface" use nothing else, while "bagged" needs a g and "zebra" needs a z.

Example 2

Input: allowed = "xy", words = ["z", "xx", "yyy", "xyxy"]
Output: 3

A letter may be repeated as often as needed, so the last three all work. Only "z" is out of reach.

Example 3

Input: allowed = "a", words = ["b", "c", "d"]
Output: 0

None of the labels use the single letter on hand.

Constraints

1 <= words.length <= 10^4
1 <= allowed.length <= 26
1 <= words[i].length <= 10
The letters in allowed are all different
allowed and every entry of words consist 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 count_consistent_strings(allowed: str, words: list[str]) -> int:

Java

public int countConsistentStrings(String allowed, String[] words)

The intended approach

Time O(A + total) for an allowed set of size A and total label length, since each character is read once.Space O(1): two integers regardless of how many labels arrive.

There are only twenty-six letters, so the whole set of type on hand fits in one integer used as a row of switches, with the bit for a letter turned on when the press holds it. A label is settable exactly when the same row built from its own letters turns on nothing outside that set, which one bitwise test decides. Build the allowed row once, then fold each label into a row and count the labels whose row has nothing left over.

Pythonentry point: count_consistent_strings

def count_consistent_strings(allowed, words):
    have = 0
    for ch in allowed:
        have |= 1 << (ord(ch) - 97)
    settable = 0
    for word in words:
        need = 0
        for ch in word:
            need |= 1 << (ord(ch) - 97)
        if need & ~have == 0:
            settable += 1
    return settable

The obvious version

For each label, take each of its letters and search the allowed string from the start looking for it, rejecting the label at the first letter not found. No bit rows and no sets.

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_count_consistent_strings(allowed, words):
    settable = 0
    for word in words:
        ok = True
        for ch in word:
            found = False
            for other in allowed:
                if other == ch:
                    found = True
                    break
            if not found:
                ok = False
                break
        if ok:
            settable += 1
    return settable

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