Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution:
- def maxLength(self, arr: List[str]) -> int:
- # Remove words with duplicate letters
- arr = [s for s in arr if len(s) == len(set(s))]
- def to_letters_bitset(s: str) -> int:
- ret = 0
- for c in s:
- ret |= 1 << (ord(c) - ord('a'))
- return ret
- letters = [to_letters_bitset(s) for s in arr]
- ans = 0
- comb = 1
- MAX_COMB = 2 ** len(arr)
- while comb < MAX_COMB:
- comb_inc = 1
- cur_letters = 0
- cur_len = 0
- for i in range(len(arr) - 1, -1, -1):
- cur_bit = 2 ** i
- if (cur_bit & comb) == 0:
- continue
- if (cur_letters & letters[i]) != 0:
- comb -= comb & (2 ** (i + 1) - 1)
- comb_inc = cur_bit * 2
- break
- cur_letters |= letters[i]
- cur_len += len(arr[i])
- # We don't have to care if comb is valid as used_letters and
- # cur_len are only increased when we have a valid prefix of comb
- ans = max(ans, cur_len)
- comb += comb_inc
- return ans
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement