Bit Manipulation - Maximum Product of Word Lengths

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.

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: "abcw" and "xtfn" share no common letters, and 4 * 4 = 16.

Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: "abc" and "d" share no letters, 3 * 1 = 3; "ab" and "cd" give 4.

Represent each word as a bitmask of 26 bits where bit i is set if character 'a'+i appears in the word. Two words share no common letters if and only if the AND of their bitmasks is 0.

Build a bitmask for each word by setting bit (c - 'a') for each character c.
For every pair (i, j), check if mask[i] & mask[j] == 0.
If no common letters, update the maximum with words[i].length() * words[j].length().

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

Complexity Analysis:

Time complexity: O(n^2 + L) where L is total characters across all words.
Space complexity: O(n) — for the bitmask array.