Question

318. 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.

Solutions

Solution 1: Bit Manipulation

The problem requires us to find two strings without common letters, so that their length product is maximized. We can represent each string with a binary number $mask[i]$, where each bit of this binary number indicates whether the string contains a certain letter. If two strings do not have common letters, then the bitwise AND result of the two binary numbers corresponding to these strings is $0$, that is, $mask[i] \& mask[j] = 0$.

We traverse each string. For the current string $words[i]$ we are traversing, we first calculate the corresponding binary number $mask[i]$, and then traverse all strings $words[j]$ where $j \in [0, i)$. We check whether $mask[i] \& mask[j] = 0$ holds. If it holds, we update the answer to $\max(ans, |words[i]| \times |words[j]|)$.

After the traversal, we return the answer.

The time complexity is $O(n^2 + L)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string array $words$, and $L$ is the sum of the lengths of all strings in the string array.

class Solution:
  def maxProduct(self, words: List[str]) -> int:
    mask = [0] * len(words)
    ans = 0
    for i, s in enumerate(words):
      for c in s:
        mask[i] |= 1 << (ord(c) - ord("a"))
      for j, t in enumerate(words[:i]):
        if (mask[i] & mask[j]) == 0:
          ans = max(ans, len(s) * len(t))
    return ans

class Solution {
  public int maxProduct(String[] words) {
    int n = words.length;
    int[] mask = new int[n];
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (char c : words[i].toCharArray()) {
        mask[i] |= 1 << (c - 'a');
      }
      for (int j = 0; j < i; ++j) {
        if ((mask[i] & mask[j]) == 0) {
          ans = Math.max(ans, words[i].length() * words[j].length());
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int maxProduct(vector<string>& words) {
    int n = words.size();
    int mask[n];
    memset(mask, 0, sizeof(mask));
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (char& c : words[i]) {
        mask[i] |= 1 << (c - 'a');
      }
      for (int j = 0; j < i; ++j) {
        if ((mask[i] & mask[j]) == 0) {
          ans = max(ans, (int) (words[i].size() * words[j].size()));
        }
      }
    }
    return ans;
  }
};

func maxProduct(words []string) (ans int) {
  n := len(words)
  mask := make([]int, n)
  for i, s := range words {
    for _, c := range s {
      mask[i] |= 1 << (c - 'a')
    }
    for j, t := range words[:i] {
      if mask[i]&mask[j] == 0 {
        ans = max(ans, len(s)*len(t))
      }
    }
  }
  return
}

function maxProduct(words: string[]): number {
  const n = words.length;
  const mask: number[] = Array(n).fill(0);
  let ans = 0;
  for (let i = 0; i < n; ++i) {
    for (const c of words[i]) {
      mask[i] |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
    }
    for (let j = 0; j < i; ++j) {
      if ((mask[i] & mask[j]) === 0) {
        ans = Math.max(ans, words[i].length * words[j].length);
      }
    }
  }
  return ans;
}

Solution 2

class Solution:
  def maxProduct(self, words: List[str]) -> int:
    mask = defaultdict(int)
    ans = 0
    for s in words:
      a = len(s)
      x = 0
      for c in s:
        x |= 1 << (ord(c) - ord("a"))
      for y, b in mask.items():
        if (x & y) == 0:
          ans = max(ans, a * b)
      mask[x] = max(mask[x], a)
    return ans

class Solution {
  public int maxProduct(String[] words) {
    Map<Integer, Integer> mask = new HashMap<>();
    int ans = 0;
    for (var s : words) {
      int a = s.length();
      int x = 0;
      for (char c : s.toCharArray()) {
        x |= 1 << (c - 'a');
      }
      for (var e : mask.entrySet()) {
        int y = e.getKey(), b = e.getValue();
        if ((x & y) == 0) {
          ans = Math.max(ans, a * b);
        }
      }
      mask.merge(x, a, Math::max);
    }
    return ans;
  }
}

class Solution {
public:
  int maxProduct(vector<string>& words) {
    unordered_map<int, int> mask;
    int ans = 0;
    for (auto& s : words) {
      int a = s.size();
      int x = 0;
      for (char& c : s) {
        x |= 1 << (c - 'a');
      }
      for (auto& [y, b] : mask) {
        if ((x & y) == 0) {
          ans = max(ans, a * b);
        }
      }
      mask[x] = max(mask[x], a);
    }
    return ans;
  }
};

func maxProduct(words []string) (ans int) {
  mask := map[int]int{}
  for _, s := range words {
    a := len(s)
    x := 0
    for _, c := range s {
      x |= 1 << (c - 'a')
    }
    for y, b := range mask {
      if x&y == 0 {
        ans = max(ans, a*b)
      }
    }
    mask[x] = max(mask[x], a)
  }
  return
}

function maxProduct(words: string[]): number {
  const mask: Map<number, number> = new Map();
  let ans = 0;
  for (const s of words) {
    const a = s.length;
    let x = 0;
    for (const c of s) {
      x |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
    }
    for (const [y, b] of mask.entries()) {
      if ((x & y) === 0) {
        ans = Math.max(ans, a * b);
      }
    }
    mask.set(x, Math.max(mask.get(x) || 0, a));
  }
  return ans;
}