Sponsored
Sponsored
This approach uses bit manipulation to represent each word with a bitmask where each bit corresponds to a character ('a' to 'z'). This allows comparison of character sets in constant time using a bitwise AND operation. If two words have no common characters, their corresponding bitmask AND result should be zero.
Time Complexity: O(N^2 + L), where N is the number of words and L is the total number of characters across all words.
Space Complexity: O(N), as we require an array to store bit masks for each word.
1public class Solution {
2 public int maxProduct(String[] words) {
3 int n = words.length;
4 int[] masks = new int[n];
5 int maxProduct = 0;
6
7 for (int i = 0; i < n; i++) {
8 for (char c : words[i].toCharArray()) {
9 masks[i] |= 1 << (c - 'a');
10 }
11 }
12
13 for (int i = 0; i < n; i++) {
14 for (int j = i + 1; j < n; j++) {
15 if ((masks[i] & masks[j]) == 0) {
16 maxProduct = Math.max(maxProduct, words[i].length() * words[j].length());
17 }
18 }
19 }
20
21 return maxProduct;
22 }
23}
24In Java, each word is converted to a bitmask that encodes the presence of characters. The solution then loops through all pairs of words, using bitwise AND to determine if they share any letters. The maximum product of non-overlapping pairs is calculated and returned.
This approach involves iterating through each pair of words, using a set to represent the characters of each word. For each pair, it checks if there are any common letters using set intersection. This method is straightforward but less efficient than bit manipulation for larger input sizes.
Time Complexity: O(N^2 * L) where L is the average length of the words.
Space Complexity: O(N * L) as each word is stored in a set.
1class Solution:
2 def maxProduct(self
In this Python solution, each word is converted into a set of characters. The method then goes through each pair of words and checks for common letters using set intersection. If no common letters exist—and thereby the intersection is an empty set—it calculates their length product and updates the maximum product.