Show problems as
Classic problem #1239MediumArrayStringBacktrackingBit Manipulation

Maximum Length of a Concatenated String with Unique Characters

Real-world version: Longest Stencil Run Without A Repeated Letter
Tracked in this browser only
Read Maximum Length of a Concatenated String with Unique Characters on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_unique_run(strips: list[str]) -> int:
Java
public int maxUniqueRun(String[] strips)

More on the same topics