https://leetcode.com/problems/maximum-product-of-word-lengths/

Question

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

int in Java has 32 bits and we only have lower case letters which are 26 in total. We can use the position of the bits in the int as index for the character, eg: index 0 is character ‘a’, 1 is ‘b’ … 25 is ‘z’ and use the value of in that position to flag weather the word has that character. So, the int we are using is essentially an boolean[] of size 26 but the boolean[size] will cost size * 1 byte of space since the size of boolean is 1 byte in Java.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int maxProduct(String[] words) {
        int[] chars = new int[words.length];
        for (int l = 0; l < words.length; l++) {
            int j = 0;
            for (int i = 0; i < words[l].length(); i++) {
                j |= 1 << (words[l].charAt(i) - 'a');
            }
            chars[l] = j;
        }
        int max = 0;
        for (int i = 0; i < words.length - 1; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((chars[i] & chars[j]) == 0) {
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }
        return max;
        
    }
}

Follow up: what if we use upper and lower case of letters?

Use a boolean[] to store the information we need but it’s hard to do bitwise operation and takes a lot of space.

We can use BitSet from java.util, it provides all the bitwise operation and boolean size is 1 bit.