Skip to content

318. Maximum Product of Word Lengths 👍

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int maxProduct(String[] words) {
    int ans = 0;
    int[] masks = new int[words.length]; // "abd" -> 0b1011

    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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def maxProduct(self, words: list[str]) -> int:
    ans = 0

    def getMask(word: str) -> int:
      mask = 0
      for c in word:
        mask |= 1 << string.ascii_lowercase.index(c)
      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