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
The two words can be
16The two words can be
"abcw", "xtfn".
Example 2:
Given
Return
The two words can be
["a", "ab", "abc", "d", "cd", "bcd", "abcd"]Return
4The two words can be
"ab", "cd".
Example 3:
Given
Return
No such pair of words.
Solution["a", "aa", "aaa", "aaaa"]Return
0No such pair of words.
If you first read the problem, you can think of brute force solution: for each pair of words, check whether they have a common letter, if not, get the product of their lengths and compare to max value achieved so far.
The brute force solution leads to another requirement: checking a pair of words if they contain common letters? Actually, we can do that with some pre-calculation, and with the understanding that the words contain only lowercase letters.
Since there are only 26 lowercase letters, we can represent a set of letters using an integer. So let's say if the word contains 'a', then the integer's 0th bit will be 1. If it has 'b', then the 1st is set to 1, so on and so forth.
Below is the Java code with simple implementation.
I. Simple Solution
public class Solution {
//In this code, I used dietpepsi as array's name to give credit to dietpepsi ^_^
public int maxProduct(String[] words) {
int n = words.length;
int[] dietpepsi = new int[n];
for(int i=0; i<n; i++){
dietpepsi[i] = getMask(words[i]);
}
int max = 0; int t;
for(int i=0; i<n; i++){
t = 0;
for(int j=i+1; j<n; j++){
if((dietpepsi[i] & dietpepsi[j]) == 0){
t = Math.max(t, words[j].length());
}
}
max = Math.max(max, t*words[i].length());
}
return max;
}
private int getMask(String s){
int mask = 0;
for(char c: s.toCharArray()){
mask |= 1 << (c - 'a');
}
return mask;
}
}
II. Improvement on (I) We can make some improvement by first sorting the words according to their lengths. Then for the ith word in the sorted array, we check from i-1 to 0 to see if there is a word that shares no common letter with it. Then we calculate the product, compare to the max value so far, stop the loop for the ith word, and move on with the (i+1)th word.
public class Solution {
public int maxProduct(String[] words) {
int n = words.length;
Arrays.sort(words, new LengthComparator());
int[][] dietpepsi = new int[n][2];
int max = 0;
for(int i=0; i<n; i++){
dietpepsi[i][0] |= getMask(words[i]);
dietpepsi[i][1] = words[i].length();
}
int last = 0;
for(int i=n-1; i>=1; i--){
for(int j=i-1; j>=last; j--){
if((dietpepsi[i][0] & dietpepsi[j][0]) == 0){
max = Math.max(dietpepsi[i][1] * dietpepsi[j][1], max);
last = j;
while(last<n && dietpepsi[last][1]==dietpepsi[j][1]) last++;
break;
}
}
}
return max;
}
private int getMask(String s){
int mask = 0;
for(char c: s.toCharArray()){
mask |= 1 << (c - 'a');
}
return mask;
}
class LengthComparator implements Comparator<String>{
public int compare(String a, String b){
return a.length() - b.length();
}
}
}
PS: Do you think there is a O( NLgN) or O(N) solution for this problem?
