Maximum Product of Word Lengths

Problem

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.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

Solution

Bit Manipulation Solution

public class Solution {
    public int maxProduct(String[] words) {
        if (words == null || words.length < 2) return 0;
        int len = words.length;
        int[] values = new int[len];
        for (int i = 0; i < len; i++) {
            String word = words[i];
            for (char ch : word.toCharArray()) values[i] |= 1 << (ch - 'a'); 
        }
        int max = 0;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if ((values[i] & values[j]) == 0) max = Math.max(words[i].length() * words[j].length(), max);
            }
        }
        return max;
    }
}

Analysis

The tricky part of this solution is to determine if two word share common letters
We use Bit Manipulation cause there are at most 26 characters
For 'a', we store it as 1 bit, for 'b' we store it as two bits
Hence we use << left shit 1 ('a' -> 1, 'b' -> 2, 'c' - > 4, ..., 'z' -> 2 ^ 25)
Since each char will occupy one bit, we then use |= to store all letters from each word
Then we use two loops, and get the max product
We check whether they share common letters by doing values[i] & values[j]