318. Maximum Product of Word Lengths #

Problem #

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.

Problem Statement #

Given a string array words, find the maximum value of length(word[i]) * length(word[j]), where these two words do not contain any common letters. You may assume that each word contains only lowercase letters. If no such two words exist, return 0.

Solution Approach #

• Find 2 strings in the string array that have no common characters, and the product of the lengths of these two strings must be the largest. Find this maximum product.
• Here we need to use the property of the bitwise & operation. If X & Y = 0, it means X and Y are completely different. Therefore, we encode all strings into binary numbers and perform the & operation to identify strings with no common characters, then dynamically maintain the maximum value of the length product. The rule for encoding a string into a binary number is relatively simple: for each character, calculate its distance from ‘a’, and shift 1 left by that many bits according to this distance.

    a 1->1  
    b 2->10  
    c 4->100  
    ab 3->11  
    ac 5->101  
    abc 7->111  
    az 33554433->10000000000000000000000001  

Code #

package leetcode

func maxProduct318(words []string) int {
	if words == nil || len(words) == 0 {
		return 0
	}
	length, value, maxProduct := len(words), make([]int, len(words)), 0
	for i := 0; i < length; i++ {
		tmp := words[i]
		value[i] = 0
		for j := 0; j < len(tmp); j++ {
			value[i] |= 1 << (tmp[j] - 'a')
		}
	}
	for i := 0; i < length; i++ {
		for j := i + 1; j < length; j++ {
			if (value[i]&value[j]) == 0 && (len(words[i])*len(words[j]) > maxProduct) {
				maxProduct = len(words[i]) * len(words[j])
			}
		}
	}
	return maxProduct
}