318. Maximum Product of Word Lengths

/ Chu Rong

https://leetcode.com/problems/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
No such pair of words.

 

Solution:

The intuition for solving this problem is to compare each pair of words. The complexity of iterating each pair of words is O(n^2). If we compare each character in two words, there will be an additional O(k^2) complexity. (n is the number of words, k is the  length of a word).

Thus, The brutal force solution is time consuming. So we need to find out a way to decrease the complexity of previous two steps. The comparison between each two words is hard to optimize, since the words are arbitrary. However, there is a trick we can do on the comparison of characters in each word.

The idea is use an integer’s lower 26 bits to present a character of a word. if a character exists in a word, the bit that represent that word will be 1, otherwise 0. Thus, after this pre-processing, when we and any two integers, if there do not have same characters, the result will be 0, otherwise will be 1.

Hence, the complexity of character’s comparison will be O(1), which make the whole time complexity be O(n^2). This is acceptable.

Here is the code:


/*
bit manipulation.

*/
public class Solution {
    public int maxProduct(String[] words) {
        int len = words.length;
        int max = 0;
        if(len == 0) return 0;
        int[] biVals = new int[len];
  // pre-processing each word, use an integer's lower 26 bits to present a word's characters.
        for(int i = 0; i < len; i++) {
            biVals[i] = 0;
            for(char ch : words[i].toCharArray()) {
                biVals[i] |= 1 << (ch - 'a');
            }
        }
    // compare each pair of words in O(n^2).
        for( int i = 0; i < len; i++) {
            for(int j = i+1; j < len; j++) {                 if(((biVals[i] & biVals[j]) == 0) && (words[i].length() * words[j].length() > max))
                    max = words[i].length() * words[j].length();
            }
        }
        return max;
    }
}

 

 

 

Leave a comment