No-Repeat Letter Banner
MediumBit Manipulation
Problem
A sign maker owns a box of letter tiles with exactly one tile per letter a–z. A customer offers a list of lowercase words; the sign maker may pick any subset of them (keeping their order) and print them side by side on a banner, using one tile per character.
Since every letter has a single tile, no letter may appear twice on the banner. Return the maximum number of characters on a valid banner.
Example 1
- Input:
- words = ["sky", "bar", "ten", "bus"]
- Output:
- 9
sky + bar + ten uses nine distinct letters; bus clashes with both sky and bar.
Example 2
- Input:
- words = ["aa", "bb"]
- Output:
- 0
Each word repeats a letter on its own, so the only valid banner is empty.
Example 3
- Input:
- words = ["ab", "ba", "cd"]
- Output:
- 4
Constraints
- 1 ≤ words.length ≤ 16
- 1 ≤ words[i].length ≤ 26
- words[i] contains lowercase English letters only.
Hint
Show the first hint
Represent each word by a 26-bit mask of its letters. When can two masks sit on the same banner?
Walkthrough
How to approach it
01Clarify before coding
- Must the chosen words keep their order? Order does not change the letter count, so only the subset matters.
- Can a single word repeat a letter? Yes, and then that word can never be used.
- Is the empty banner allowed? Yes, so the answer is at least 0.
02Brute force
Try all 2^n subsets, concatenate the words and check with a set whether all characters are distinct.
Cost: O(2^n · L) with L up to 26 · 16 characters per subset: around 2.7 · 10^7 character operations. Works but rebuilds strings and sets for every subset.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.