Disjoint Word-Pair Score
MediumBit Manipulation
Problem
A word game scores a pair of words by multiplying their lengths, but only if the two words share no letter at all.
Given a list of lowercase words, return the best score over all pairs of different positions. Return 0 if no pair qualifies.
Example 1
- Input:
- words = ["code", "lamp", "fish", "bird"]
- Output:
- 16
code and lamp share no letter: 4 · 4.
Example 2
- Input:
- words = ["ant", "tan", "nat"]
- Output:
- 0
Example 3
- Input:
- words = ["zebra", "quilt", "mock", "vow", "ivy", "gnu"]
- Output:
- 25
Constraints
- 2 ≤ words.length ≤ 1000
- 1 ≤ words[i].length ≤ 1000
- Lowercase English letters only.
Hint
Show the first hint
Comparing two words letter by letter is slow. How can you test 'no shared letter' in one step?
Walkthrough
How to approach it
01Clarify before coding
- Can a word pair with itself? No, the two positions must differ.
- Do repeated letters inside one word matter? No, only the set of letters matters for disjointness; the score uses the full length.
- What if nothing qualifies? Return 0.
02Brute force
For every pair, build a set from one word and test each character of the other.
Cost: O(n² · L) with L up to 1000: about 5 · 10^8 character checks at the limits.
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.