Maximum Product of Word Lengths (Leetcode 318)

Difficulty: Medium Link: Day 27: May Leetcode Challenge

Problem Statement

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

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".
Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".
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

The important thing to note here is that letters should not be common among the two strings but can be duplicate in itself. This is important if you decide to use sets to check if they have letters in common. Since sets reduces to unique values the set count of combined string would be less than individual set counts. However since letters can be duplicate inside the string so set will reduce them as well.

We can try the solution and checking pairwise for every string if they have no common letters and saving the max length. However, this is already a O(N2) operation and if we are performance O(L) operations on strings then complexity would shoot upwards of O(N2). We need a strategy to precompute the results and then only check pair-wise which will keep our solution under O(N2).

Bitmasking

Since letters are only given as lowercase english letters, the number of different alphabets can be only 26. We can use a bit-mask of 26 digits to mask the occurrence the any letter. Bitmasks can help us to determine if two strings share a common letter in O(1) which is a significant optimisation from O(L1 + L2). We can simple apply ‘&’ operator on two bitmasks and if result is 0 then there is no common letter. Bitwise AND would be zero if all bits are difference hence no letter map to the same bit offset.

To save the results, we can cache them in a dictionary mapping bit-mask to its length. Also note, that multiple words can have same bitmasks (“ab”, “aaab”, “abbbb”). So we only need to keep the word with the longest length for optimal result.

Bit masking words

Swift

class Solution {
func maxProduct(_ words: [String]) -> Int {
var maxLength = 0
var bitMap = [Int:Int]()
for word in words{
let bitMask = getBitMask(word)
// Multiple words can have same bitmasks (a , aaaaaa).
// We need to keep the max length only
if let currentLength = bitMap[bitMask] {
bitMap[bitMask] = max(currentLength, word.count)
}
else{
bitMap[bitMask] = word.count
}
}
for i in bitMap.keys{
for j in bitMap.keys{
if i & j == 0 {
maxLength = max(maxLength, bitMap[i]!*bitMap[j]!)
}
}
}
return maxLength
}
func getBitMask(_ str:String) -> Int {
var bitMask = 0
for char in str{
let maskOffset = getAsciiOffset(char)
bitMask |= 1 << maskOffset
}
return bitMask
}
func getAsciiOffset(_ char:Character) -> Int{
return Int(char.asciiValue!) 97
}
}

Java

class Solution {
public int bitNumber(char ch){
return (int)ch (int)'a';
}
public int maxProduct(String[] words) {
Map<Integer, Integer> hashmap = new HashMap();
int bitmask = 0, bitNum = 0;
for (String word : words) {
bitmask = 0;
for (char ch : word.toCharArray()) {
// add bit number bitNumber in bitmask
bitmask |= 1 << bitNumber(ch);
}
// there could be different words with the same bitmask
// ex. ab and aabb
hashmap.put(bitmask, Math.max(hashmap.getOrDefault(bitmask, 0), word.length()));
}
int maxProd = 0;
for (int x : hashmap.keySet())
for (int y : hashmap.keySet())
if ((x & y) == 0) maxProd = Math.max(maxProd, hashmap.get(x) * hashmap.get(y));
return maxProd;
}
}

Python

from collections import defaultdict
class Solution:
def maxProduct(self, words: List[str]) -> int:
hashmap = defaultdict(int)
bit_number = lambda ch : ord(ch) ord('a')
for word in words:
bitmask = 0
for ch in word:
# add bit number bit_number in bitmask
bitmask |= 1 << bit_number(ch)
# there could be different words with the same bitmask
# ex. ab and aabb
hashmap[bitmask] = max(hashmap[bitmask], len(word))
max_prod = 0
for x in hashmap:
for y in hashmap:
if x & y == 0:
max_prod = max(max_prod, hashmap[x] * hashmap[y])
return max_prod

Complexity Analysis

In the worst case, bit mask of every value would be unique and we would be to check pair-wise which would be O(N2). We are also iterating through every word for bit mask value conversion and in case N is small but string lengths are very big (L > N2), then complexity would be bounded by the total length of all strings L.

Time = O(N2 + L) // Where N is number of strings and L is total count of lengths.

Space = O(N) // Every Bitmask needs to be stored.

Leave a Reply

Your email address will not be published. Required fields are marked *