Maximum Product of Word Lengths - Practice Coding Problems

Maximum Product of Word Lengths - Problem

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 & Output

Example 1 — Basic Case

$ Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]

› Output: 16

💡 Note: The two words can be "abcw" and "xtfn". "abcw" has letters {a,b,c,w} and "xtfn" has letters {x,t,f,n}. No common letters, so product = 4 × 4 = 16.

Example 2 — No Valid Pairs

$ Input: words = ["a","ab","abc","d","cd","bcd","abcd"]

› Output: 4

💡 Note: The two words can be "ab" and "cd". "ab" has letters {a,b} and "cd" has letters {c,d}. No overlap, product = 2 × 2 = 4.

Example 3 — All Words Share Letters

$ Input: words = ["a","aa","aaa","aaaa"]

› Output: 0

💡 Note: All words contain the letter 'a', so no two words can be chosen without sharing common letters.

Constraints

2 ≤ words.length ≤ 1000
1 ≤ words[i].length ≤ 1000
words[i] consists only of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words: ["abcw","baz","foo","bar","xtfn","abcdef"]

Process

Find pairs with no common letters, calculate length products

Output

Maximum product: "abcw" × "xtfn" = 4 × 4 = 16

Key Takeaway

🎯 Key Insight: Use bitmasks to convert O(m×n) character comparison to O(1) bitwise AND operation

Asked in

G Google 45 f Facebook 38 M Microsoft 32 a Amazon 28

The key insight is to use bitmasks to represent character sets, enabling O(1) overlap checking via bitwise AND. Best approach uses bit manipulation for ultra-fast comparisons. Time: O(n² + n×m), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Character Set Optimization	O(n² × m)	O(n × m)	Convert words to sets for faster overlap detection
Bitmask Optimization	O(n² + n×m)	O(n)	Use bitmasks to represent character sets for O(1) comparisons
Brute Force Character Comparison	O(n² × m²)	O(1)	Check every pair of words by comparing all characters

Character Set Optimization — Algorithm Steps

Convert each word to a character set
Compare pairs using set intersection
Calculate product for non-overlapping pairs
Track maximum product

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Sets

Convert each word to a character set

Set Intersection

Check if sets have common elements

Calculate Product

Multiply lengths if no intersection

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(char words[][21], int n) {
    int maxProduct = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Create character frequency arrays
            bool chars_i[26] = {false};
            bool chars_j[26] = {false};
            
            for (int k = 0; words[i][k]; k++) {
                chars_i[words[i][k] - 'a'] = true;
            }
            for (int k = 0; words[j][k]; k++) {
                chars_j[words[j][k] - 'a'] = true;
            }
            
            // Check for intersection
            bool hasCommon = false;
            for (int k = 0; k < 26; k++) {
                if (chars_i[k] && chars_j[k]) {
                    hasCommon = true;
                    break;
                }
            }
            
            if (!hasCommon) {
                int product = strlen(words[i]) * strlen(words[j]);
                if (product > maxProduct) {
                    maxProduct = product;
                }
            }
        }
    }
    
    return maxProduct;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char words[300][21];
    int n = 0;
    
    char *token = strtok(line, "[\"],");
    while (token != NULL && n < 300) {
        if (token[0] == '"') {
            strcpy(words[n], token + 1);
            words[n][strlen(words[n]) - 1] = '\0';
            n++;
        }
        token = strtok(NULL, "[\"],");
    }
    
    int result = solution(words, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m)

n² pairs, each set intersection takes O(m) where m is average word length

⚠ Quadratic Growth

Space Complexity

O(n × m)

Storing character sets for all n words, each with up to m characters

⚡ Linearithmic Space

78.0K Views

Medium Frequency

~15 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Character Set Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler