Maximum Value Of A String In An Array - Leetcode Solution

Problem Description:

Given an array of strings 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.

Solution:

To find the maximum length multiplied by two different strings in an array, we need to go through all pairs of the strings in the array and check if they have any common letters or not. If they don't have any common letters, we will calculate the product of their lengths and check if it's the largest one so far.

To check if two strings have any common letters or not, we can use a bitmask. We will create a bitmask for each string, where each bit represents the presence or absence of a letter in the string. We will use bit manipulation to check if two bitmasks have any common bits or not.

Algorithm:

1. Initialize max_product = 0
2. For each pair of strings i and j in the array words: a. Initialize mask_i and mask_j as zero b. For each letter in string i, set the corresponding bit in mask_i to 1 c. For each letter in string j, set the corresponding bit in mask_j to 1 d. if (mask_i & mask_j) == 0, then update max_product as max(max_product, len(i)*len(j))
3. Return max_product

Code:

We can use the built-in ord() function in Python to convert a character to its ASCII value, which we can use to set or check bits in a bitmask. Here's the Python code for solving this problem:

def maxProduct(words): max_product = 0 for i in range(len(words)): mask_i = 0 for c in words[i]: mask_i |= 1 << ord(c) - ord('a') for j in range(i+1, len(words)): mask_j = 0 for c in words[j]: mask_j |= 1 << ord(c) - ord('a') if mask_i & mask_j == 0: max_product = max(max_product, len(words[i]) * len(words[j])) return max_product

Time Complexity:

This algorithm has time complexity of O(n^2 * L), where n is the number of strings in the array and L is the maximum length of a string. The nested loop iterates over all pairs of strings, and the inner loop iterates over each letter in a string, which takes O(L) time.

1