Jobs

Interviews

Discussions

Maximum Product of Word Lengths

#1830 Most AskedMedium

Maximum Product of Word Lengths #1830 Most Asked

Medium

Google

6 views

Topics:

ArraysStringsBit Manipulation

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.

Try coding it in LeetCode

Maximum Product of Word Lengths

#1830 Most AskedMedium

Maximum Product of Word Lengths #1830 Most Asked

Medium

Google

6 views

Topics:

ArraysStringsBit Manipulation

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array `words` contain null or empty strings?
What is the maximum length of a single word in the input array?
If no two words have disjoint characters, should I return 0?
Are the input words guaranteed to be lowercase, or can they contain uppercase letters or other characters?
Is there a limit to the number of words in the input array?

Brute Force Solution

Approach

The goal is to find two words that don't share any letters and whose lengths, when multiplied, give the biggest result. The brute force way is to check all possible pairs of words to see if they fit the requirements.

Here's how the algorithm would work step-by-step:

Take the first word in the list.
Compare it to every other word in the list.
For each comparison, check if the two words share any letters in common.
If the two words do not share any letters, calculate the result of multiplying their lengths together.
Remember the biggest product you have seen so far.
Move to the next word in the list and repeat the process, comparing it to all the other words.
Keep doing this until you have compared every word with every other word.
The biggest product you have remembered throughout this process will be your answer.

Code Implementation

def maximum_product_of_word_lengths_brute_force(words):
    maximum_product = 0

    for first_word_index in range(len(words)):
        first_word = words[first_word_index]

        for second_word_index in range(len(words)):
            second_word = words[second_word_index]

            # Avoid comparing a word to itself
            if first_word_index == second_word_index:
                continue

            share_common_letters = False
            for letter in first_word:
                if letter in second_word:
                    # If they share common letters, mark it down
                    share_common_letters = True

                    break

            if not share_common_letters:
                # Only calculate product if no shared letters

                product = len(first_word) * len(second_word)

                # Track the largest product seen so far

                if product > maximum_product:
                    maximum_product = product

    return maximum_product

Big(O) Analysis

Time Complexity

O(n² * m) – Let n be the number of words in the input list and m be the average length of the words. The algorithm iterates through all possible pairs of words, resulting in approximately n * n/2 pairs. For each pair, it checks if the two words share any common letters. Comparing two words for common letters takes O(m) time in the worst case, where m is the average word length. Thus the total time complexity is approximately n * n/2 * m, which simplifies to O(n² * m).

Space Complexity

O(1) – The provided solution checks all possible pairs of words and keeps track of the maximum product seen so far. It uses a constant number of variables to store the current word indices and the maximum product. Therefore, the auxiliary space used does not depend on the input size N (the number of words) and remains constant.

Optimal Solution

Approach

The goal is to find two words that don't share any letters and whose lengths multiplied together give the largest possible product. Instead of directly comparing each pair of words to every other word, we'll use a clever way to represent each word's letters to speed up the process.

Here's how the algorithm would work step-by-step:

First, for each word, create a simple representation that tells you which letters of the alphabet are present in the word. Think of it like a little flag for each letter from 'a' to 'z'.
Now, go through all possible pairs of words.
For each pair, quickly check if they share any letters by comparing their representations. If they do share a letter, skip to the next pair.
If they don't share any letters, calculate the product of their lengths.
Keep track of the largest product you've found so far.
After checking all pairs, the largest product you tracked is the answer.

Code Implementation

def maximum_product_of_word_lengths(words):
    word_representations = []

    for word in words:
        representation = 0
        for char in word:
            representation |= (1 << (ord(char) - ord('a')))
        word_representations.append(representation)

    max_product = 0

    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            # Check if the two words have common letters.
            if (word_representations[i] & word_representations[j]) == 0:

                current_product = len(words[i]) * len(words[j])
                # Track the maximum product found so far.
                max_product = max(max_product, current_product)

    return max_product

Big(O) Analysis

Time Complexity

O(n^2) – Let n be the number of words in the input array. The algorithm iterates through all possible pairs of words. For each word, it calculates its bitmask representation, which takes O(m) where m is the average length of a word, which is considered constant for this problem. Then it compares each pair of words, resulting in approximately n * (n-1) / 2 comparisons. Each comparison involves checking if the bitmasks have any common bits, taking O(1) time. Therefore, the overall time complexity is dominated by the pair comparisons, approximating n * n/2, simplifying to O(n^2).

Space Complexity

O(N) – The algorithm creates a representation for each word to indicate which letters are present. If N is the number of words, we store N representations. Each representation uses a fixed amount of space (e.g., an integer or boolean array of size 26) which is constant. Therefore, the auxiliary space used is proportional to the number of words N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as no product is possible.
Array containing only empty strings	Return 0 because the product of any lengths with a 0 is 0.
Array containing a single word	Return 0 because you need at least two words to form a product.
All words in the array share at least one common character.	The maximum product should be 0 since no disjoint words are available.
Very long words causing integer overflow of the product.	Use a 64-bit integer type or appropriate overflow handling to prevent incorrect results.
Maximum number of words in the input array.	Ensure the solution's time complexity remains acceptable when approaching the maximum word count.
Words with non-ASCII characters.	Handle unicode characters correctly when creating bitmasks or checking for common characters; a bitmask may not be sufficient.
Words with the same set of characters but different ordering.	The bitmask or other character-set representation should handle this correctly, preventing such words from being considered disjoint.

Empty input array

How to Handle:

Return 0 immediately as no product is possible.

Array containing only empty strings

How to Handle:

Return 0 because the product of any lengths with a 0 is 0.

Array containing a single word

How to Handle:

Return 0 because you need at least two words to form a product.

All words in the array share at least one common character.

How to Handle:

The maximum product should be 0 since no disjoint words are available.

Very long words causing integer overflow of the product.

How to Handle:

Use a 64-bit integer type or appropriate overflow handling to prevent incorrect results.

Maximum number of words in the input array.

How to Handle:

Ensure the solution's time complexity remains acceptable when approaching the maximum word count.

Words with non-ASCII characters.

How to Handle:

Handle unicode characters correctly when creating bitmasks or checking for common characters; a bitmask may not be sufficient.

Words with the same set of characters but different ordering.

How to Handle:

The bitmask or other character-set representation should handle this correctly, preventing such words from being considered disjoint.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array `words` contain null or empty strings?
What is the maximum length of a single word in the input array?
If no two words have disjoint characters, should I return 0?
Are the input words guaranteed to be lowercase, or can they contain uppercase letters or other characters?
Is there a limit to the number of words in the input array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first word in the list.
Compare it to every other word in the list.
For each comparison, check if the two words share any letters in common.
If the two words do not share any letters, calculate the result of multiplying their lengths together.
Remember the biggest product you have seen so far.
Move to the next word in the list and repeat the process, comparing it to all the other words.
Keep doing this until you have compared every word with every other word.
The biggest product you have remembered throughout this process will be your answer.

Code Implementation

def maximum_product_of_word_lengths_brute_force(words):
    maximum_product = 0

    for first_word_index in range(len(words)):
        first_word = words[first_word_index]

        for second_word_index in range(len(words)):
            second_word = words[second_word_index]

            # Avoid comparing a word to itself
            if first_word_index == second_word_index:
                continue

            share_common_letters = False
            for letter in first_word:
                if letter in second_word:
                    # If they share common letters, mark it down
                    share_common_letters = True

                    break

            if not share_common_letters:
                # Only calculate product if no shared letters

                product = len(first_word) * len(second_word)

                # Track the largest product seen so far

                if product > maximum_product:
                    maximum_product = product

    return maximum_product

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, for each word, create a simple representation that tells you which letters of the alphabet are present in the word. Think of it like a little flag for each letter from 'a' to 'z'.
Now, go through all possible pairs of words.
For each pair, quickly check if they share any letters by comparing their representations. If they do share a letter, skip to the next pair.
If they don't share any letters, calculate the product of their lengths.
Keep track of the largest product you've found so far.
After checking all pairs, the largest product you tracked is the answer.

Code Implementation

def maximum_product_of_word_lengths(words):
    word_representations = []

    for word in words:
        representation = 0
        for char in word:
            representation |= (1 << (ord(char) - ord('a')))
        word_representations.append(representation)

    max_product = 0

    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            # Check if the two words have common letters.
            if (word_representations[i] & word_representations[j]) == 0:

                current_product = len(words[i]) * len(words[j])
                # Track the maximum product found so far.
                max_product = max(max_product, current_product)

    return max_product

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as no product is possible.
Array containing only empty strings	Return 0 because the product of any lengths with a 0 is 0.
Array containing a single word	Return 0 because you need at least two words to form a product.
All words in the array share at least one common character.	The maximum product should be 0 since no disjoint words are available.
Very long words causing integer overflow of the product.	Use a 64-bit integer type or appropriate overflow handling to prevent incorrect results.
Maximum number of words in the input array.	Ensure the solution's time complexity remains acceptable when approaching the maximum word count.
Words with non-ASCII characters.	Handle unicode characters correctly when creating bitmasks or checking for common characters; a bitmask may not be sufficient.
Words with the same set of characters but different ordering.	The bitmask or other character-set representation should handle this correctly, preventing such words from being considered disjoint.

Empty input array

How to Handle:

Return 0 immediately as no product is possible.

Array containing only empty strings

How to Handle:

Return 0 because the product of any lengths with a 0 is 0.

Array containing a single word

How to Handle:

Return 0 because you need at least two words to form a product.

All words in the array share at least one common character.

How to Handle:

The maximum product should be 0 since no disjoint words are available.

Very long words causing integer overflow of the product.

How to Handle:

Use a 64-bit integer type or appropriate overflow handling to prevent incorrect results.

Maximum number of words in the input array.

How to Handle:

Ensure the solution's time complexity remains acceptable when approaching the maximum word count.

Words with non-ASCII characters.

How to Handle:

Handle unicode characters correctly when creating bitmasks or checking for common characters; a bitmask may not be sufficient.

Words with the same set of characters but different ordering.

How to Handle:

The bitmask or other character-set representation should handle this correctly, preventing such words from being considered disjoint.

0/1916 Google questions completed

0/1916 completed