Given a string array

`words`

, find the maximum value of `length(word[i]) * length(word[j])`

where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Example 1:

Given

Return

The two words can be

`["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]`

Return

`16`

The two words can be

`"abcw", "xtfn"`

.
Example 2:

Given

Return

The two words can be

`["a", "ab", "abc", "d", "cd", "bcd", "abcd"]`

Return

`4`

The two words can be

`"ab", "cd"`

.
Example 3:

Given

Return

No such pair of words.

`["a", "aa", "aaa", "aaaa"]`

Return

`0`

No such pair of words.

**Understand the problem:**

The problem is a little bit ambiguous. The two words used to calculate the product of length must not share any common characters. e.g. word1 = abc, word2 = bcd, the product is 0 not 1, because they share common chars.

The most straight-forward way to solve this problem is to pick up any two words, and check if they have common characters. If not, then calculate the maximum product of the length.

Now let's analyze the complexity in time. Suppose the number of words is n, and average word length is m. So the time complexity for the brute-force solution is O(n^2 * m).

**A better approach using bit manipulation:**

Now let's think can we reduce the time complexity when we check the intersection of two words?

Since each word contains 26 characters in lower case only. We can use a bit map to encode the string. Since we only need 26 bits for a word, it is enough to use an integer to encode a string.

**Code (Java):**

public class Solution { public int maxProduct(String[] words) { if (words == null || words.length <= 1) { return 0; } int n = words.length; int[] encodedWords = new int[n]; for (int i = 0; i < words.length; i++) { String word = words[i]; for (int j = 0; j < word.length(); j++) { char c = word.charAt(j); encodedWords[i] |= (1 << (c - 'a')); } } int maxLen = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if ((encodedWords[i] & encodedWords[j]) == 0) { maxLen = Math.max(maxLen, words[i].length() * words[j].length()); } } } return maxLen; } }

**Analysis:**

Compared to the brute force solution, the time complexity of the bit solution is O(26 * n^2), which is O(n^2). If m >> 26, the bit solution is better.

ReplyDeleteNew DietTaps into Pioneering Plan to Help Dieters Get Rid Of 12-23 Pounds in Just 21 Days!