318. 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.

class Solution { public: int maxPRoduct(vector<string>& words) { int size = words.size(), max = 0; for(int i = 0; i < size - 1; ++i){ int len1= words[i].length(); int t[26] = {0}; for(char ch : words[i]) t[ch - 'a'] = 1; for(int j = i + 1; j < size; ++j){ int len2 = words[j].length(); if(len1 * len2 > max){ int k = 0; for( ; k < len2; ++k) if(t[words[j][k] - 'a']) break; if(k == len2) max = len2 * len1; } } } return max; } };