Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 1239 with 16 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1239 # by problem number
lcpy gen -s maximum_length_of_a_concatenated_string_with_unique_characters # by problem name
arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.
Return the maximum possible length of s.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All the valid concatenations are:
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
Maximum length is 4.
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").
Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26
Explanation: The only string in arr has all 26 characters.
1 <= arr.length <= 161 <= arr[i].length <= 26arr[i] contains only lowercase English letters.class Solution:
# Time: O(2^n * n) worst case
# Space: O(n)
def max_len(self, arr: list[str]) -> int:
masks: list[int] = []
for s in arr:
mask = 0
for char in s:
bit = 1 << (ord(char) - ord("a"))
if mask & bit:
break
mask |= bit
else:
masks.append(mask)
best = 0
def dfs(i: int, current: int) -> None:
nonlocal best
best = max(best, current.bit_count())
for j in range(i, len(masks)):
if not (current & masks[j]):
dfs(j + 1, current | masks[j])
dfs(0, 0)
return best
| Time | Space |
|---|---|
| O(2^n * n) worst case | O(n) |