> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0318-maximum-product-of-word-lengths.md).

# 0318. Maximum Product of Word Lengths

<https://leetcode.com/problems/maximum-product-of-word-lengths>

## Description

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.

## ac

```java
class Solution {
    public int maxProduct(String[] words) {
        // edge cases
        if (words.length <= 1) return 0;

        // 1) get a bit mask represent letter used for each word
        int[] masks = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            int mask = 0;
            for (char c : words[i].toCharArray()) {
                int b = c - 'a';
                mask |= 1 << b;
            }
            masks[i] = mask;
        }

        // 2) check every pair get max product
        int max = 0;
        for (int i = 0; i < words.length - 1; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((masks[i] & masks[j]) != 0) continue; // have common letters
                max = Math.max(max, words[i].length() * words[j].length());
            }
        }

        return max;
    }
}

/*
1) get a bit mask represent letter used for each word 2) check every pair get max product
*/
```