318. Maximum Product of Word Len

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.

Example 1:

Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be `"abcw", "xtfn".

Example 2:

Input: ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be `"ab", "cd".

Example 3:

Input: ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.

Solution

HashMap, O(N ^ 2 * L), S(N ^ 2)

Use char2Index to keep the word indexes of words that contains char x.
For each word, use noCommon set to keep no common word indexes. Iterate each char c in word[i], remove the indexes of char2Index.get(c) from noCommon set. Finally noCommon contains no common indexes only. Then calculate maxProduct.

class Solution {
    public int maxProduct(String[] words) {
        if (words == null || words.length < 2) {
            return 0;
        }
        
        Map<Character, Set<Integer>> char2Index = new HashMap<>();
        int n = words.length;
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < words[i].length(); ++j) {
                char c = words[i].charAt(j);
                
                if (!char2Index.containsKey(c)) {
                    char2Index.put(c, new HashSet<>());
                }
                
                char2Index.get(c).add(i);
            }
        }
        
        int maxProduct = 0;
        
        for (int i = 0; i < n; ++i) {
            Set<Integer> noCommon = new HashSet<>();
            for (int j = 0; j < n; ++j) {   // add [0, n - 1] initially
                noCommon.add(j);
            }
            
            for (int j = 0; j < words[i].length(); ++j) {
                noCommon.removeAll(char2Index.get(words[i].charAt(j)));
            }
            
            for (int j : noCommon) {
                maxProduct = Math.max(
                    words[i].length() * words[j].length(), maxProduct);
            }
        }
        
        return maxProduct;
    }
}

Bit-manipulation, O(n ^ 2), S(n)

Because words only contains lowercase letters (26 in total), we could use 1 bit to mark each char appearance. Then we could use just one int bits to represent a word. If words[i] and words[j] share no char, bits[i] & bits[j] should equal to 1.

class Solution {
    public int maxProduct(String[] words) {
        if (words == null || words.length < 2) {
            return 0;
        }
        
        int n = words.length;
        int[] bits = new int[n];
        // use bits[i] to represent words[i]
        // each bit is a mark of a character appearance
        for (int i = 0; i < n; ++i) {
            String s = words[i];
            for (int j = 0; j < s.length(); ++j) {
                bits[i] |= 1 << (s.charAt(j) - 'a');
            }
        }
        
        int maxProduct = 0;
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((bits[i] & bits[j]) == 0) {
                    maxProduct = Math.max(
                        words[i].length() * words[j].length(), maxProduct);
                }
            }
        }
        
        return maxProduct;
    }
}