How to Find Maximum Product of Word Lengths?

Submit your solution at Leetcode: maximum product of word lengths

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

O(n^2) C++ solution

We can represent the usage of letters for each words using an 32-bit integer. Because there are only lowercase letters, so a 32-bit integer is enough for storing the appearance (yes or no) for a word.

1
2
3
4

int k = 0;
for (int j = 0; j < words[i].length(); j ++) {
    k = k | (1 <<(char)(words[i].at(j)));
}

int k = 0;
for (int j = 0; j < words[i].length(); j ++) {
    k = k | (1 <<(char)(words[i].at(j)));
}

Then, we can compare with O(n^2) loop, note that the total length for two words is the same regardless the order of multiplication.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int len = words.size();
        int *num = new int[len];
        // compute the bit O(n)
        for (int i = 0; i < len; i ++) {
            int k = 0;
            for (int j = 0; j < words[i].length(); j ++) {
                k = k | (1 <<(char)(words[i].at(j)));
            }
            num[i] = k;
        }
        int c = 0;
        // O(n^2)
        for (int i = 0; i < len - 1; i ++) {
            for (int j = i + 1; j < len; j ++) {
                if ((num[i] & num[j]) == 0) { // if no common letters
                    int x = words[i].length() * words[j].length();
                    if (x > c) {
                        c = x;
                    }
                }
            }
        }
        delete []num;
        return c;
    }
};

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int len = words.size();
        int *num = new int[len];
        // compute the bit O(n)
        for (int i = 0; i < len; i ++) {
            int k = 0;
            for (int j = 0; j < words[i].length(); j ++) {
                k = k | (1 <<(char)(words[i].at(j)));
            }
            num[i] = k;
        }
        int c = 0;
        // O(n^2)
        for (int i = 0; i < len - 1; i ++) {
            for (int j = i + 1; j < len; j ++) {
                if ((num[i] & num[j]) == 0) { // if no common letters
                    int x = words[i].length() * words[j].length();
                    if (x > c) {
                        c = x;
                    }
                }
            }
        }
        delete []num;
        return c;
    }
};

The solution passes 174 test cases within 108ms on Leetcode online judge.

–EOF (The Ultimate Computing & Technology Blog) —