BinarySearch 0335 Max Character Distinct Words

Problem statement

https://binarysearch.com/problems/Max-Character-Distinct-Words/

Solution

For each word compute its mask, then check all pairs of masks.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, words):
        masks, n, ans = [], len(words), 0
        for word in words:
            masks += [reduce(lambda x, y: x|y, [1<<(ord(w) - 97) for w in word])]
        
        for i, j in combinations(range(n), 2):
            if not masks[i] & masks[j]:
                ans = max(ans, len(words[i]) + len(words[j]))

        return ans