Задача: 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.

😎 Решение:

public 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 bitmask = 0;
            foreach (char ch in words[i]) {
                bitmask |= 1 << (ch - 'a');
            }
            masks[i] = bitmask;
            lens[i] = words[i].Length;
        }
        
        int maxVal = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxVal = Math.Max(maxVal, lens[i] * lens[j]);
                }
            }
        }
        return maxVal;
    }
}

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