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
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"] Output: 16 Explanation: The two words can be "abcw", "xtfn".
Input: words = ["a","ab","abc","d","cd","bcd","abcd"] Output: 4 Explanation: The two words can be "ab", "cd".
Input: words = ["a","aa","aaa","aaaa"] Output: 0 Explanation: No such pair of words.
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i]consists only of lowercase English letters.
The important thing to note here is that letters should not be common among the two strings but can be duplicate in itself. This is important if you decide to use sets to check if they have letters in common. Since sets reduces to unique values the set count of combined string would be less than individual set counts. However since letters can be duplicate inside the string so set will reduce them as well.
We can try the solution and checking pairwise for every string if they have no common letters and saving the max length. However, this is already a O(N2) operation and if we are performance O(L) operations on strings then complexity would shoot upwards of O(N2). We need a strategy to precompute the results and then only check pair-wise which will keep our solution under O(N2).
Since letters are only given as lowercase english letters, the number of different alphabets can be only 26. We can use a bit-mask of 26 digits to mask the occurrence the any letter. Bitmasks can help us to determine if two strings share a common letter in O(1) which is a significant optimisation from O(L1 + L2). We can simple apply ‘&’ operator on two bitmasks and if result is 0 then there is no common letter. Bitwise AND would be zero if all bits are difference hence no letter map to the same bit offset.
To save the results, we can cache them in a dictionary mapping bit-mask to its length. Also note, that multiple words can have same bitmasks (“ab”, “aaab”, “abbbb”). So we only need to keep the word with the longest length for optimal result.
In the worst case, bit mask of every value would be unique and we would be to check pair-wise which would be O(N2). We are also iterating through every word for bit mask value conversion and in case N is small but string lengths are very big (L > N2), then complexity would be bounded by the total length of all strings L.
Time = O(N2 + L) // Where N is number of strings and L is total count of lengths.
Space = O(N) // Every Bitmask needs to be stored.