Maximum Product of Word Lengths LeetCode Solution

Maximum Product of Word Lengths 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.

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.

Maximum Product of Word Lengths Solutions

✅Time: O(n)
✅Space: O(n)

C++

class Solution {
 public:
  int maxProduct(vector<string>& words) {
    size_t ans = 0;
    vector<int> masks;

    for (const string& word : words)
      masks.push_back(getMask(word));

    for (int i = 0; i < words.size(); ++i)
      for (int j = 0; j < i; ++j)
        if ((masks[i] & masks[j]) == 0)
          ans = max(ans, words[i].length() * words[j].length());

    return ans;
  }

 private:
  int getMask(const string& word) {
    int mask = 0;
    for (const char c : word)
      mask |= 1 << c - 'a';
    return mask;
  }
};

Java

 class Solution {
  public int maxProduct(String[] words) {
    int ans = 0;
    int[] masks = new int[words.length]; // "abd" -> (1011)2

    for (int i = 0; i < words.length; ++i)
      masks[i] = getMask(words[i]);

    for (int i = 0; i < masks.length; ++i)
      for (int j = 0; j < i; ++j)
        if ((masks[i] & masks[j]) == 0)
          ans = Math.max(ans, words[i].length() * words[j].length());

    return ans;
  }

  private int getMask(final String word) {
    int mask = 0;
    for (final char c : word.toCharArray())
      mask |= 1 << c - 'a';
    return mask;
  }
}

Python

 class Solution:
  def maxProduct(self, words: List[str]) -> int:
    ans = 0

    def getMask(word: str) -> int:
      mask = 0
      for c in word:
        mask |= 1 << ord(c) - ord('a')
      return mask

    masks = [getMask(word) for word in words]

    for i in range(len(words)):
      for j in range(i):
        if not (masks[i] & masks[j]):
          ans = max(ans, len(words[i]) * len(words[j]))

    return ans

Watch Tutorial

Checkout more Solutions here