• 42.8%

https://leetcode.com/problems/maximum-product-of-word-lengths/?tab=Description

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

#### cpp

https://discuss.leetcode.com/topic/31766/bit-shorter-c

Bit shorter C++

Same algorithm as most, just written a bit shorter.

Update: Here’s an O(n+N) variation, where n is the number of words and N is the total number of characters in all words. Thanks to junhuangli for the suggestion.

Or: (thanks to junhuangli’s further comment)

https://discuss.leetcode.com/topic/31753/116ms-c-solution-use-early-pruning-faster-than-most-o-n-2

116ms c++ solution use early pruning (faster than most O(N^2))

Sort the vector first according to the length of string. Then use some early pruning to fasten the process.

The worst cases would still be O(N^2). It’s faster than most O(N^2) solutions. I don’t know whether we can do better. (Binary Search Seems Not work here) Any comments is welcomed.

Update: We can use counting sort to improve the time complexity of sorting to O(N).

https://discuss.leetcode.com/topic/40001/c-25-lines-96ms-straight-forward-solution

C++, 25 lines, 96ms, straight-forward solution

#### python

https://discuss.leetcode.com/topic/46685/python-solution-beats-99-67

Python solution, beats 99.67%

#### java

https://discuss.leetcode.com/topic/35539/java-easy-version-to-understand

JAVA———-Easy Version To Understand!!!!!!!!!!!!!!!!!

https://discuss.leetcode.com/topic/31769/32ms-java-ac-solution

32ms Java AC solution

https://discuss.leetcode.com/topic/31739/bit-manipulation-java-o-n-2

Bit manipulation Java O(n^2)

Pre-process the word, use bit to represent the words. We can do this because we only need to compare if two words contains the same characters.