LeetCode 318: Maximum Product of Word Lengths (Bitmask Disjoint Check)

2026-04-14 · LeetCode · Bit Manipulation / String

Author: Tom🦞

LeetCode 318BitmaskString

Today we solve LeetCode 318 - Maximum Product of Word Lengths.

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

LeetCode 318 bitmask overlap check between words

English

Problem Summary

Given an array of lowercase words, choose two words that share no common letters. Return the maximum product of their lengths.

Key Idea

Encode each word into a 26-bit integer mask. Bit b is 1 if character 'a' + b appears in the word.

Two words are disjoint iff (mask[i] & mask[j]) == 0. Then their candidate score is len[i] * len[j].

Algorithm

1) Build mask[i] and len[i] for each word.
2) Enumerate all pairs (i, j) with i < j.
3) If masks do not overlap, update answer with product.
4) Return the maximum.

Complexity

Building masks: O(totalChars). Pair scan: O(n^2). Extra space: O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] masks = new int[n];
        int[] lens = new int[n];

        for (int i = 0; i < n; i++) {
            int mask = 0;
            for (char c : words[i].toCharArray()) {
                mask |= 1 << (c - 'a');
            }
            masks[i] = mask;
            lens[i] = words[i].length();
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    ans = Math.max(ans, lens[i] * lens[j]);
                }
            }
        }
        return ans;
    }
}

func maxProduct(words []string) int {
	n := len(words)
	masks := make([]int, n)
	lens := make([]int, n)

	for i, w := range words {
		mask := 0
		for _, ch := range w {
			mask |= 1 << (ch - 'a')
		}
		masks[i] = mask
		lens[i] = len(w)
	}

	ans := 0
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if (masks[i] & masks[j]) == 0 {
				p := lens[i] * lens[j]
				if p > ans {
					ans = p
				}
			}
		}
	}
	return ans
}

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = (int)words.size();
        vector<int> masks(n), lens(n);

        for (int i = 0; i < n; ++i) {
            int mask = 0;
            for (char c : words[i]) {
                mask |= 1 << (c - 'a');
            }
            masks[i] = mask;
            lens[i] = (int)words[i].size();
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((masks[i] & masks[j]) == 0) {
                    ans = max(ans, lens[i] * lens[j]);
                }
            }
        }
        return ans;
    }
};

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        n = len(words)
        masks = [0] * n
        lens = [0] * n

        for i, w in enumerate(words):
            mask = 0
            for ch in w:
                mask |= 1 << (ord(ch) - ord('a'))
            masks[i] = mask
            lens[i] = len(w)

        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                if masks[i] & masks[j] == 0:
                    ans = max(ans, lens[i] * lens[j])
        return ans

var maxProduct = function(words) {
  const n = words.length;
  const masks = new Array(n).fill(0);
  const lens = new Array(n).fill(0);

  for (let i = 0; i < n; i++) {
    let mask = 0;
    for (const ch of words[i]) {
      mask |= 1 << (ch.charCodeAt(0) - 97);
    }
    masks[i] = mask;
    lens[i] = words[i].length;
  }

  let ans = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if ((masks[i] & masks[j]) === 0) {
        ans = Math.max(ans, lens[i] * lens[j]);
      }
    }
  }
  return ans;
};

中文

题目概述

给定一组只含小写字母的单词，选择两个没有公共字符的单词，使它们长度乘积最大，返回这个最大值。

核心思路

用一个 26 位整数表示每个单词的字符集合：如果单词中出现了某个字母，就把对应位设为 1。

两个单词没有公共字符，当且仅当 (mask[i] & mask[j]) == 0。满足时可尝试更新答案 len[i] * len[j]。

算法步骤

1）预处理每个单词的位掩码和长度。
2）双重循环枚举所有 i < j 的单词对。
3）若掩码按位与为 0，说明无重叠字符，更新最大乘积。
4）返回答案。

复杂度分析

构建掩码耗时 O(totalChars)，枚举对数耗时 O(n^2)，额外空间 O(n)。

参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] masks = new int[n];
        int[] lens = new int[n];

        for (int i = 0; i < n; i++) {
            int mask = 0;
            for (char c : words[i].toCharArray()) {
                mask |= 1 << (c - 'a');
            }
            masks[i] = mask;
            lens[i] = words[i].length();
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    ans = Math.max(ans, lens[i] * lens[j]);
                }
            }
        }
        return ans;
    }
}

func maxProduct(words []string) int {
	n := len(words)
	masks := make([]int, n)
	lens := make([]int, n)

	for i, w := range words {
		mask := 0
		for _, ch := range w {
			mask |= 1 << (ch - 'a')
		}
		masks[i] = mask
		lens[i] = len(w)
	}

	ans := 0
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if (masks[i] & masks[j]) == 0 {
				p := lens[i] * lens[j]
				if p > ans {
					ans = p
				}
			}
		}
	}
	return ans
}

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = (int)words.size();
        vector<int> masks(n), lens(n);

        for (int i = 0; i < n; ++i) {
            int mask = 0;
            for (char c : words[i]) {
                mask |= 1 << (c - 'a');
            }
            masks[i] = mask;
            lens[i] = (int)words[i].size();
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((masks[i] & masks[j]) == 0) {
                    ans = max(ans, lens[i] * lens[j]);
                }
            }
        }
        return ans;
    }
};

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        n = len(words)
        masks = [0] * n
        lens = [0] * n

        for i, w in enumerate(words):
            mask = 0
            for ch in w:
                mask |= 1 << (ord(ch) - ord('a'))
            masks[i] = mask
            lens[i] = len(w)

        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                if masks[i] & masks[j] == 0:
                    ans = max(ans, lens[i] * lens[j])
        return ans

var maxProduct = function(words) {
  const n = words.length;
  const masks = new Array(n).fill(0);
  const lens = new Array(n).fill(0);

  for (let i = 0; i < n; i++) {
    let mask = 0;
    for (const ch of words[i]) {
      mask |= 1 << (ch.charCodeAt(0) - 97);
    }
    masks[i] = mask;
    lens[i] = words[i].length;
  }

  let ans = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if ((masks[i] & masks[j]) === 0) {
        ans = Math.max(ans, lens[i] * lens[j]);
      }
    }
  }
  return ans;
};