Задача: 318. Maximum Product of Word Lengths
Сложность: medium

Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0.

Пример:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

👨‍💻 Алгоритм:

1⃣Предварительная обработка масок и длин
Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens.

2⃣Сравнение слов и проверка общих букв
Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd.

3⃣Возврат результата
Верните максимальное значение произведения maxProd.

😎 Решение:

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 bitmask = 0;
        for (const ch of words[i]) {
            bitmask |= 1 << (ch.charCodeAt(0) - 'a'.charCodeAt(0));
        }
        masks[i] = bitmask;
        lens[i] = words[i].length;
    }
    
    let maxVal = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if ((masks[i] & masks[j]) === 0) {
                maxVal = Math.max(maxVal, lens[i] * lens[j]);
            }
        }
    }
    return maxVal;
};

Ставь 👍 и забирай 📚 Базу знаний