Problem Description
Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.
Key Insights
- Each word can be represented as a bitmask of 26 bits, where each bit corresponds to a letter in the alphabet.
- Two words share common letters if their bitmasks have any bits in common (i.e., the bitwise AND of their bitmasks is not zero).
- Calculate the product of lengths of pairs of words whose bitmasks do not intersect.
- The maximum product can be computed efficiently using nested loops over the words.
Space and Time Complexity
Time Complexity: O(n^2) where n is the number of words. Each pair of words is checked for common letters. Space Complexity: O(n) for storing the lengths and bitmasks of the words.
Solution
To solve this problem, we use a bit manipulation approach. Each word is converted to a bitmask where each bit represents whether a corresponding letter (from 'a' to 'z') is present in the word. We then compare the bitmasks of every pair of words. If the bitwise AND of two bitmasks is zero, it means the words do not share any letters. We calculate the product of their lengths and keep track of the maximum product found.