Maximum Product of Word Lengths

LeetCode 318 | Difficulty: Medium

Medium

Problem Description

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.

Topics: Array, String, Bit Manipulation

---

Approach

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 124 ms)

Metric	Value
Runtime	124 ms
Memory	N/A
Date	2018-08-19

Solution

public class Solution {
    public int MaxProduct(string[] words)
{
    int len = words.Length;
    int[] values = new int[len];
    for (int i = 0; i < len; i++)
    {
        foreach (var c in words[i])
        {
            values[i] |= 1 << (c-'a');
        }
    }
    int max = 0;
    for (int i = 0; i < len-1; i++)
    {
        for (int j = i+1; j < len; j++)
        {
            if((values[i]&values[j])==0)
            {
                max = Math.Max(words[i].Length*words[j].Length,max);
            }
        }
    }
    return max;

}
}

📜 1 more C# submission(s)

Submission (2018-08-19) — 188 ms, N/A

public class Solution {
    public int MaxProduct(string[] words)
{
    int len = words.Length;
    int[][] values = new int[len][];
    for (int i = 0; i < len; i++)
    {
        values[i] = new int[26];
        foreach (var c in words[i])
        {
            if (values[i][c - 'a'] == 0)
            {
                (values[i][c - 'a'])++;
            }
        }
    }

    int max = 0;
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = i + 1; j < len; j++)
        {
            bool sharesChar = false;
            for (int k = 0; k < 26; k++)
            {
                if (values[i][k] != 0 && values[i][k]==values[j][k])
                {
                    sharesChar = true; break;
                }   
                
            }
            if(!sharesChar)
            max = Math.Max(words[i].Length * words[j].Length, max);
        }
    }
    return max;

}
}

---

Complexity Analysis

Approach	Time	Space
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.