algoadvance

You are given an array of strings words. Each word consists of lowercase English letters.

Your task is to 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 lowercase letters. If no such two words exist, return 0.

Example:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

Clarifying Questions

  1. Q: Are the words case-sensitive? A: No, each word consists of only lowercase English letters.

  2. Q: Is there a limit on the number of words or their lengths? A: For the sake of this problem, you may assume that the number of words and the length of each word are reasonably large to fit into memory.

  3. Q: Can words in the input list be empty strings? A: No, the problem does not specify that there can be empty strings.

Strategy

  1. Bitmask Representation: Use bitmasking to represent each word. Each bit in a 26-bit integer represents whether a particular letter (‘a’ to ‘z’) is present in the word or not. This allows us to quickly check if two words share any common letter by performing a bitwise AND operation.

  2. Store Word Lengths and Bitmasks: For each word, compute its bitmask and store it along with its length.

  3. Max Product Calculation: Iterate through each pair of words. Use their bitmasks to determine if they share common letters. If they do not, calculate the product of their lengths and update the maximum product found.

Code

def maxProduct(words):
    def word_to_bitmask(word):
        bitmask = 0
        for char in word:
            bitmask |= 1 << (ord(char) - ord('a'))
        return bitmask
    
    n = len(words)
    bitmasks = [0] * n
    lengths = [0] * n
    
    for i in range(n):
        bitmasks[i] = word_to_bitmask(words[i])
        lengths[i] = len(words[i])
    
    max_product = 0
    
    for i in range(n):
        for j in range(i + 1, n):
            if bitmasks[i] & bitmasks[j] == 0:
                max_product = max(max_product, lengths[i] * lengths[j])
    
    return max_product

# Example usage
words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
print(maxProduct(words))  # Output: 16

Time Complexity

Preprocessing: Converting each word to a bitmask takes O(1) per character, and there are at most 26 characters. Hence, for n words, the preprocessing step is O(n * k), where k is the maximum length of a word.

Comparisons: Checking all pairs of words takes O(n^2) time.

Overall, the time complexity is O(n * k + n^2). Given that k (the length of the word) is relatively small and constant, the complexity is effectively O(n^2) in the worst case, which is manageable for reasonably large inputs.

Try our interview co-pilot at AlgoAdvance.com