0742MediumArrayStringBacktrackingBit Manipulation

Longest Stencil Run Without A Repeated Letter

Tracked in this browser only

Trains the technique from

LeetCode 1239Maximum Length of a Concatenated String with Unique Characters

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 print shop owns a rack of stencil strips, strips[i] being the lowercase text engraved on strip i. To make a banner the shop picks some of the strips, keeping them in rack order, and butts the chosen texts together into one run.

A run is only printable when no letter shows up twice anywhere in it. That rules out reusing a letter across two chosen strips, and it also rules out any strip whose own engraving repeats a letter: such a strip cannot appear in a printable run at all, not even on its own.

The shop may pick as many or as few strips as it likes, including none, and a run made of no strips has length 0.

Return the greatest length a printable run can have.

Examples

Example 1

Input: strips = ["fox", "glib", "fog"]
Output: 7

Picking strips 0 and 1 gives the run `"foxglib"`, which is seven characters long and uses each of `f`, `o`, `x`, `g`, `l`, `i`, `b` once.

Example 2

Input: strips = ["mummy", "pen", "quid"]
Output: 7

Strip 0 engraves `m` three times, so it cannot appear in any printable run. Picking strips 1 and 2 gives `"penquid"`, seven characters with no letter twice.

Example 3

Input: strips = ["aa", "bb"]
Output: 0

Both strips repeat a letter within their own engraving, so neither may be picked and the only printable run is the empty one.

Constraints

1 <= strips.length <= 16
1 <= strips[i].length <= 26
strips[i] 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 max_unique_run(strips: list[str]) -> int:

Java

public int maxUniqueRun(String[] strips)

The intended approach

Time O(n * 2^n) for n strips, plus O(total engraved length) to build the masks.Space O(2^n) for the collection of reachable masks.

Only the set of letters a run covers matters, never their order, so represent a run by a 26-bit mask with one bit per letter. Convert each strip to a mask while checking that its own letters are distinct, and drop a strip whose engraving already repeats a letter. Keep a growing collection of masks that are reachable, seeded with the empty run. For each usable strip, pair it with every mask reachable so far whose bits do not overlap it and record the combined mask, tracking the largest bit count seen. Because the strips are handled one at a time, every subset of usable strips is reached exactly once.

Pythonentry point: max_unique_run

def max_unique_run(strips):
    # a strip is usable only if its own letters are distinct, so encode each
    # usable strip as a 26-bit letter set and grow the collection of reachable
    # letter sets one strip at a time.
    # O(n * 2^n) time, O(2^n) space for n strips.
    reachable = [0]
    best = 0
    for text in strips:
        bits = 0
        clean = True
        for ch in text:
            b = 1 << (ord(ch) - 97)
            if bits & b:
                clean = False
                break
            bits |= b
        if not clean:
            continue
        grown = []
        for have in reachable:
            if have & bits:
                continue
            merged = have | bits
            grown.append(merged)
            width = bin(merged).count("1")
            if width > best:
                best = width
        reachable.extend(grown)
    return best

The obvious version

Enumerate all 2^n selections of strips, glue the chosen texts into one character list, and keep the longest list whose characters are all different. No masks and no incremental structure.

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_max_unique_run(strips):
    """Try every selection of strips, glue the chosen texts together and keep the
    longest glued text whose characters are all different."""
    n = len(strips)
    best = 0
    for choice in range(1 << n):
        glued = []
        for i in range(n):
            if choice >> i & 1:
                glued.extend(strips[i])
        if len(set(glued)) == len(glued) and len(glued) > best:
            best = len(glued)
    return best

How this problem was checked

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