Problem
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
.
Examples
Example 1:
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".
Example 2:
Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".
Example 3:
Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.
Constraints
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i]
consists only of lowercase English letters.
Solution
Method 1 - Using Hashset and Intersection
Here is the approach:
- Create Sets for Each Word:
- For each word in the input list, create a set of its characters. This will help in quickly checking for common characters between words.
- Compare Each Pair of Words:
- Iterate through all possible pairs of words. For each pair, check if the two sets of characters have any intersection.
- If the sets are disjoint (no common characters), calculate the product of the lengths of these two words.
- Track the Maximum Product:
- Keep track of the maximum product found during the comparisons.
- Return the maximum product as the result.
But the above solution now gives TLE.
Code
Java
public int maxProduct(String[] words) {
List<Set<Character>> listOfSet = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
String word = words[i];
Set<Character> set = new HashSet<>();
for (char c: word.toCharArray()) {
set.add(c);
}
listOfSet.add(set);//added at ith index
}
int max = 0;
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
Set<Character> intersection = new HashSet<>(listOfSet.get(j));
intersection.retainAll(listOfSet.get(i));
if (intersection.isEmpty()) {
max = Math.max(max, words[i].length() * words[j].length());
}
}
}
return max;
}
Python
class Solution:
def maxProduct(self, words: List[str]) -> int:
list_of_sets: List[Set[str]] = []
# Create list of sets for each word
for word in words:
char_set = set(word)
list_of_sets.append(char_set)
max_product = 0
# Compare each pair of words
for i in range(len(words)):
for j in range(i + 1, len(words)):
if list_of_sets[i].isdisjoint(list_of_sets[j]):
max_product = max(max_product, len(words[i]) * len(words[j]))
return max_product
Complexity
- ⏰ Time complexity:
O(n^2 * m)
, wheren
is the number of words andm
is the average length of the words. This accounts for creating sets and checking for common characters. - 🧺 Space complexity:
O(n * m)
, for storing the sets of characters for each word.
Method 2 - Convert String to Binary Representation Based on Prescence of Char
Since the string contains only lowercase characters from a
to z
, we can convert the string to a binary representation. If a character like a
is present, we set the 0th bit from the right, and if z
is present, we set the 25th bit from the right. We can use an integer for this representation.
To set the bit, we use the operation: arr[i] |= (1 << (c - 'a'));
For example:
// a 1 -> 1
// b 2 -> 10
// c 4 -> 100
// ab 3 -> 11
// ac 5 -> 101
// abc 7 -> 111
// az 33554433 -> 10000000000000000000000001
We can then use the and operator
&
to check if two words share common letters.
Approach
- Binary Representation of Words:
- Convert each word into a binary representation where each bit represents the presence of a specific character.
- Setting Bits:
- For each character in the word, set the corresponding bit in an integer.
- Calculate Maximum Product:
- Use nested loops to compare the binary representations of all pairs of words.
- If two words do not share any characters (checked using the
&
operator), calculate their product and update the maximum product if necessary.
Code
Java
public int maxProduct(String[] words) {
if (words == null || words.length == 0)
return 0;
int[] arr = new int[words.length];
for (int i = 0; i<words.length; i++) {
for (int j = 0; j<words[i].length(); j++) {
char c = words[i].charAt(j);
arr[i] |= (1<< (c - 'a'));
}
}
int ans = 0;
for (int i = 0; i<words.length; i++) {
for (int j = i + 1; j<words.length; j++) {
if ((arr[i] & arr[j]) == 0) {
ans = Math.max(ans, words[i].length() * words[j].length());
}
}
}
return ans;
}
Python
class Solution:
def maxProduct(self, words: List[str]) -> int:
if not words:
return 0
n = len(words)
arr = [0] * n
# Convert each word to its binary representation
for i in range(n):
for char in words[i]:
arr[i] |= 1 << (ord(char) - ord('a'))
max_product = 0
# Compare all pairs to find the max product
for i in range(n):
for j in range(i + 1, n):
if arr[i] & arr[j] == 0:
max_product = max(max_product, len(words[i]) * len(words[j]))
return max_product
Complexity
- ⏰ Time complexity:
O(n^2 * m)
, wheren
is the number of words andm
is the average length of the words. This accounts for converting each word to a binary representation and comparing all pairs of words. - 🧺 Space complexity:
O(n)
, for storing the binary representations of the words.