318. Maximum Product of Word Lengths

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.    

Credits:Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution

public class Solution {
  public int maxProduct(String[] words) {
        if (words == null || words.length <= 1) return 0;

        int result = 0;
        List<Word> wordList = new ArrayList<>();

        for (String s : words) {
            wordList.add(new Word(s));
        }

        for (int i = 0; i < wordList.size(); i++) {
            for (int j = i + 1; j < wordList.size(); j++) {
                if (!wordList.get(i).share(wordList.get(j))) {
                    result = Math.max(result, wordList.get(i).s.length() * wordList.get(j).s.length());
                }
            }
        }

        return result;
    }

    public class Word {
        int[] array;
        String s;

        public Word(String s) {
            this.s = s;
            this.array = new int[26];

            for (char c : s.toCharArray()) {
                array[c - 'a'] = 1;
            }
        }

        public boolean share(Word s2) {
            int[] array2 = s2.array;
            for (int i = 0; i < 26; i++) {
                if (array2[i] == 1 && array[i] == 1) {
                    return true;
                }
            }

            return false;
        }
    }
}