> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/graph-search/largest-product-of-length.md).

# Largest Product of Length

Given a dictionary containing many words, find the largest product of two words’ lengths, such that the two words do not share any common characters.

**Assumptions**

* The words only contains characters of 'a' to 'z'
* The dictionary is not null and does not contains null string, and has at least two strings
* If there is no such pair of words, just return 0

**Examples**

* dictionary = \[“abcde”, “abcd”, “ade”, “xy”], the largest product is 5 \* 2 = 10 (by choosing “abcde” and “xy”)

**Solution:** try every comb with bitMask to check for dup characters

```java
public class Solution {
  public int largestProduct(String[] dict) {
    HashMap<String, Integer> bitMasks = getBitMasks(dict);
    Arrays.sort(dict, new Comparator<String>(){
      @Override
      public int compare(String s0, String s1){
        if (s0.length() == s1.length()) return 0;
        return s0.length() < s1.length() ? 1 : -1;
      }
    });

    int largest = 0;
    for(int i = 1; i < dict.length; i++){
      for(int j = 0; j < i; j++){
        int prod = dict[i].length() * dict[j].length();
        if (prod <= largest) break;
        int iMask = bitMasks.get(dict[i]);
        int jMask = bitMasks.get(dict[j]);

        if ((iMask & jMask) == 0){
          largest = prod;
        }
      }
    }
    return largest;
  }

  private HashMap<String, Integer> getBitMasks(String[] dict){
    HashMap<String, Integer> map = new HashMap<>();
    for (String str: dict){
      int bitMask = 0;
      for (int i = 0; i < str.length(); i++){
        bitMask |= 1 << (str.charAt(i) - 'a');
      }
      map.put(str, bitMask);
    }
    return map;
  }
}

```

TC: O(N^2) check every i \* j combination

SC: O(N) Hashmap