318. Maximum Product of Word Lengths

Published on May 6, 2023

Question

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0

Algorithm

We go through all the words and see if they have common letters, if yes, we calculate the product and keep the largest one.

So the question mainly focus on how we determine if two string has common letters in an effective way. I do it firstly by a trivial way but it doesn't work. So I need to turn to other ways.

By hint, we could use a mask, to record each word bitmap, and by doing AND operation, we could know if they share common bits thus calculate the products of no sharing bits words.

Code

This code will not pass the test case due to ETL.

class Solution {
    public int maxProduct(String[] words) {
        int res = 0;
        for (int i = 0; i < words.length - 1; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (!hasCommonLetters(words[i], words[j])) {
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
    
    private boolean hasCommonLetters(String word1, String word2) {
        Set<Character> set = new HashSet<>();
        for (Character ch1 : word1.toCharArray()) {
            set.add(ch1);
        }
        Set<Character> set2 = new HashSet<>();
        for (Character ch2 : word2.toCharArray()) {
            set2.add(ch2);
        }
        for (Character ch : set) {
            if (!set2.add(ch)) {
                return true;
            }
        }
        return false;
    }
}

Code2

class Solution {
    public int maxProduct(String[] words) {
        int res = 0;
        int[] table = new int[words.length];
        
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                table[i] |= 1 << (words[i].charAt(j) - 'a');
            }
        }
        
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((table[i] & table[j]) == 0) {
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
}