Title:
Maximum Product of Word Lengths
Source: leetcode.com
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.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
/* https://leetcode.com/problems/maximum-product-of-word-lengths/ */ import java.util.*; public class MaximumProductOfWordLengths { public static void main(String args[]) { String[] words = {"abcw", "baz", "foo", "bar", "xtfn", "abcdef"}; MaximumProductOfWordLengths m = new MaximumProductOfWordLengths(); System.out.println(m.maxProduct(words)); } public int maxProduct(String[] words) { int[] a = new int[words.length]; for(int i=0;i<words.length;++i) { for(char c : words[i].toCharArray()) { //'or'ing the ascii value of all the characters //storing it in array a[i] |= 1<<(c-'a'); } } System.out.println(Arrays.toString(a)); int maxProduct = 0; for(int i = 0;i<a.length-1;++i) { for(int j = i+1;j<a.length;++j) { if((a[i]&a[j])==0) { maxProduct = Math.max(maxProduct, words[i].length() * words[j].length()); } } } return maxProduct; } } |