624. Unique Letters Concatenation
A word-game player owns a pile of tiles forming the lowercase words in words. She may pick any subset of the words (including none) and glue the picked words together in any order. The result is clean if no letter appears twice in it, counting repeats both inside a single word and across different words.
Return the greatest possible length of a clean concatenation. The empty choice has length 0. Words that already repeat a letter can never be part of a clean choice.
Example 1
- Input:
- words = ["tap","rod","stub"]
- Output:
- 7
- Explanation:
The words
tapandrodshare no letters, giving length 6; addingstubwould repeatt.
Example 2
- Input:
- words = ["aa","bb","cc"]
- Output:
- 0
- Explanation:
Every word repeats a letter, so no word can be used and the answer is 0.
Example 3
- Input:
- words = ["abcde","fgh","ijk","xyz"]
- Output:
- 14
- Explanation:
All four words use different letters, so all can be glued: 5 + 3 + 3 + 3 = 14.
Constraints
- 1 ≤
words.length≤ 20 - 1 ≤
words[i].length≤ 26 - Each word contains only lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(2^n)
- Space
- O(2^n)