Maximum product of word lengths

Array String Bit Manipulation

61.1% acceptance

Jan 12, 2026

3621

146

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_product_words(words: Vec<String>) -> i32 {
    let n = words.len();
    let mut masks = vec![0; n];
    
    for i in 0..n {
      for b in words[i].bytes() {
        masks[i] |= 1 << (b - b'a');
      }
    }
    
    let mut max_prod = 0;
    for i in 0..n {
      for j in i+1..n {
        if masks[i] & masks[j] == 0 {
          max_prod = max_prod.max((words[i].len() * words[j].len()) as i32);
        }
      }
    }
    
    max_prod
  }
}