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.
1#include<stdio.h>
2#include<string.h>
3
4int maxProduct(char **words, int wordsSize) {
5 int masks[wordsSize];
6 memset(masks, 0, sizeof(masks));
7
8 for (int i = 0; i < wordsSize; i++) {
9 for (int j = 0; words[i][j]; j++) {
10 masks[i] |= 1 << (words[i][j] - 'a');
11 }
12 }
13
14 int maxProduct = 0;
15 for (int i = 0; i < wordsSize; i++) {
16 for (int j = i + 1; j < wordsSize; j++) {
17 if ((masks[i] & masks[j]) == 0) {
18 int product = strlen(words[i]) * strlen(words[j]);
19 if (product > maxProduct) {
20 maxProduct = product;
21 }
22 }
23 }
24 }
25
26 return maxProduct;
27}
28The solution first computes a bitmask for each word using each character's position in the alphabet. Then, it iterates through all possible pairs of words, checking if their bitmasks overlap. If they do not overlap, it means the words do not share common letters, and it calculates their length product, updating the maximum product accordingly.
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.
1import java.util.*;
2
3
In this Java implementation, character sets are used to store the letters for each word. Each word pair is compared, verifying whether sets intersect. If they do not, it calculates their lengths' product and updates the maximum found.