Leetcode#318. Maximum Product of Word Lengths

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.

Example 1:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

Example 2:

Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".

Example 3:

Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.

Solution:

An integer has 32 bits and we have only 26 english letters ( ‘a’ to ‘z’ ), so if we represent every bit by a number where “1” represents the letter present and “0” represents the letter is not present in the word.

“abdf” can be represented as “00000000000000000000000000101011”.

So if we take & of two value we get common bits, means if a&b = 0 that means a and b don’t have common bits, it means that don’t have any letter common in both words.

Conclusion:

It’s always good have knowledge about bit manipulation, these make our code fast .

Thank you all …

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Vikas Shekhawat

Vikas Shekhawat

63 Followers

Sole Master | Software engineer and a happy 😊 person | Former Irresponsible Boy !!!