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.

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Example 3:

1
2
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.

Solution

Method 1 - Using Hashset and Intersection

Here is the approach:

  1. Create Sets for Each Word:
    • For each word in the input list, create a set of its characters. This will help in quickly checking for common characters between words.
  2. Compare Each Pair of Words:
    • Iterate through all possible pairs of words. For each pair, check if the two sets of characters have any intersection.
    • If the sets are disjoint (no common characters), calculate the product of the lengths of these two words.
  3. Track the Maximum Product:
    • Keep track of the maximum product found during the comparisons.
    • Return the maximum product as the result.

But the above solution now gives TLE.

Code

 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

public int maxProduct(String[] words) {
	List<Set<Character>> listOfSet = new ArrayList<>();
	for (int i = 0; i < words.length; i++) {
		String word = words[i];
		Set<Character> set = new HashSet<>();
		for (char c: word.toCharArray()) {
			set.add(c);
		}
		listOfSet.add(set);//added at ith index
	}

	int max = 0;
	for (int i = 0; i < words.length; i++) {
		for (int j = i + 1; j < words.length; j++) {
			Set<Character> intersection = new HashSet<>(listOfSet.get(j));

			intersection.retainAll(listOfSet.get(i));

			if (intersection.isEmpty()) {
				max = Math.max(max, words[i].length() * words[j].length());
			}
		}
	}
	return max;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        list_of_sets: List[Set[str]] = []
        
        # Create list of sets for each word
        for word in words:
            char_set = set(word)
            list_of_sets.append(char_set)
        
        max_product = 0
        
        # Compare each pair of words
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if list_of_sets[i].isdisjoint(list_of_sets[j]):
                    max_product = max(max_product, len(words[i]) * len(words[j]))
        
        return max_product

Complexity

  • ⏰ Time complexity: O(n^2 * m), where n is the number of words and m is the average length of the words. This accounts for creating sets and checking for common characters.
  • 🧺 Space complexity: O(n * m), for storing the sets of characters for each word.

Method 2 - Convert String to Binary Representation Based on Prescence of Char

Since the string contains only lowercase characters from a to z, we can convert the string to a binary representation. If a character like a is present, we set the 0th bit from the right, and if z is present, we set the 25th bit from the right. We can use an integer for this representation.

To set the bit, we use the operation: arr[i] |= (1 << (c - 'a')); For example:

1
2
3
4
5
6
7

         // a 1 -> 1
         // b 2 -> 10
         // c 4 -> 100
         // ab 3 -> 11
         // ac 5 -> 101
         // abc 7 -> 111
         // az 33554433 -> 10000000000000000000000001

We can then use the and operator & to check if two words share common letters.

Approach

  1. Binary Representation of Words:
    • Convert each word into a binary representation where each bit represents the presence of a specific character.
  2. Setting Bits:
    • For each character in the word, set the corresponding bit in an integer.
  3. Calculate Maximum Product:
    • Use nested loops to compare the binary representations of all pairs of words.
    • If two words do not share any characters (checked using the & operator), calculate their product and update the maximum product if necessary.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public int maxProduct(String[] words) {
	if (words == null || words.length == 0)
		return 0;

	int[] arr = new int[words.length];
	for (int i = 0; i<words.length; i++) {
		for (int j = 0; j<words[i].length(); j++) {
			char c = words[i].charAt(j);
			arr[i] |= (1<< (c - 'a'));
		}
	}

	int ans = 0;

	for (int i = 0; i<words.length; i++) {
		for (int j = i + 1; j<words.length; j++) {
			if ((arr[i] & arr[j]) == 0) {
				ans = Math.max(ans, words[i].length() * words[j].length());
			}
		}
	}

	return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        if not words:
            return 0
        
        n = len(words)
        arr = [0] * n
        
        # Convert each word to its binary representation
        for i in range(n):
            for char in words[i]:
                arr[i] |= 1 << (ord(char) - ord('a'))
        
        max_product = 0

        # Compare all pairs to find the max product
        for i in range(n):
            for j in range(i + 1, n):
                if arr[i] & arr[j] == 0:
                    max_product = max(max_product, len(words[i]) * len(words[j]))
        
        return max_product

Complexity

  • ⏰ Time complexity: O(n^2 * m), where n is the number of words and m is the average length of the words. This accounts for converting each word to a binary representation and comparing all pairs of words.
  • 🧺 Space complexity: O(n), for storing the binary representations of the words.