LeetCode //C - 318. Maximum Product of Word Lengths

318. 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.
 

Example 1:

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

Example 2:

Input: words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
Output: 4
Explanation: The two words can be “ab”, “cd”.

Example 3:

Input: words = [“a”,“aa”,“aaa”,“aaaa”]
Output: 0
Explanation: No such pair of words.

Constraints:

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] consists only of lowercase English letters.

From: LeetCode
Link: 318. Maximum Product of Word Lengths

---

Solution:

Ideas:

1. hasCommonLetters Function:

• This function uses bit manipulation to determine if two words share any common letters. Each word is represented by a 26-bit integer, where each bit corresponds to a letter (‘a’ to ‘z’).
• By iterating through each character of the words and setting the corresponding bit, we can check if any bit is set in both words using the bitwise AND operator.

2. maxProduct Function:

• The main function iterates through all pairs of words, checking if they share any common letters using the hasCommonLetters function.
• If they don’t share any letters, it calculates the product of their lengths and updates the maxProduct if the current product is greater.

3. Efficiency:

• The solution is optimized using bit manipulation to quickly check for common letters, making it suitable for larger input sizes within the given constraints.

Code:

// Function to check if two words share common letters
int hasCommonLetters(const char* word1, const char* word2) {
    int letters1 = 0, letters2 = 0;

    // Mark presence of each character in the first word
    while (*word1) {
        letters1 |= 1 << (*word1 - 'a');
        word1++;
    }

    // Mark presence of each character in the second word
    while (*word2) {
        letters2 |= 1 << (*word2 - 'a');
        word2++;
    }

    // If there is any common letter, the AND of the two will be non-zero
    return letters1 & letters2;
}

int maxProduct(char** words, int wordsSize) {
    int maxProduct = 0;

    // Iterate through all pairs of words
    for (int i = 0; i < wordsSize; i++) {
        for (int j = i + 1; j < wordsSize; j++) {
            // Check if words[i] and words[j] share common letters
            if (!hasCommonLetters(words[i], words[j])) {
                int product = strlen(words[i]) * strlen(words[j]);
                if (product > maxProduct) {
                    maxProduct = product;
                }
            }
        }
    }

    return maxProduct;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38