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 <= 10001 <= words[i].length <= 1000words[i] consists only of lowercase English letters.
Solutions#
Solution 1: Bit Manipulation#
The problem requires us to find two strings without common letters, so that their length product is maximized. We can represent each string with a binary number $mask[i]$, where each bit of this binary number indicates whether the string contains a certain letter. If two strings do not have common letters, then the bitwise AND result of the two binary numbers corresponding to these strings is $0$, that is, $mask[i] & mask[j] = 0$.
We traverse each string. For the current string $words[i]$ we are traversing, we first calculate the corresponding binary number $mask[i]$, and then traverse all strings $words[j]$ where $j \in [0, i)$. We check whether $mask[i] & mask[j] = 0$ holds. If it holds, we update the answer to $\max(ans, |words[i]| \times |words[j]|)$.
After the traversal, we return the answer.
The time complexity is $O(n^2 + L)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string array $words$, and $L$ is the sum of the lengths of all strings in the string array.
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def maxProduct(self, words: List[str]) -> int:
mask = [0] * len(words)
ans = 0
for i, s in enumerate(words):
for c in s:
mask[i] |= 1 << (ord(c) - ord("a"))
for j, t in enumerate(words[:i]):
if (mask[i] & mask[j]) == 0:
ans = max(ans, len(s) * len(t))
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int[] mask = new int[n];
int ans = 0;
for (int i = 0; i < n; ++i) {
for (char c : words[i].toCharArray()) {
mask[i] |= 1 << (c - 'a');
}
for (int j = 0; j < i; ++j) {
if ((mask[i] & mask[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
| class Solution {
public:
int maxProduct(vector<string>& words) {
int n = words.size();
int mask[n];
memset(mask, 0, sizeof(mask));
int ans = 0;
for (int i = 0; i < n; ++i) {
for (char& c : words[i]) {
mask[i] |= 1 << (c - 'a');
}
for (int j = 0; j < i; ++j) {
if ((mask[i] & mask[j]) == 0) {
ans = max(ans, (int) (words[i].size() * words[j].size()));
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| func maxProduct(words []string) (ans int) {
n := len(words)
mask := make([]int, n)
for i, s := range words {
for _, c := range s {
mask[i] |= 1 << (c - 'a')
}
for j, t := range words[:i] {
if mask[i]&mask[j] == 0 {
ans = max(ans, len(s)*len(t))
}
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function maxProduct(words: string[]): number {
const n = words.length;
const mask: number[] = Array(n).fill(0);
let ans = 0;
for (let i = 0; i < n; ++i) {
for (const c of words[i]) {
mask[i] |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
}
for (let j = 0; j < i; ++j) {
if ((mask[i] & mask[j]) === 0) {
ans = Math.max(ans, words[i].length * words[j].length);
}
}
}
return ans;
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def maxProduct(self, words: List[str]) -> int:
mask = defaultdict(int)
ans = 0
for s in words:
a = len(s)
x = 0
for c in s:
x |= 1 << (ord(c) - ord("a"))
for y, b in mask.items():
if (x & y) == 0:
ans = max(ans, a * b)
mask[x] = max(mask[x], a)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int maxProduct(String[] words) {
Map<Integer, Integer> mask = new HashMap<>();
int ans = 0;
for (var s : words) {
int a = s.length();
int x = 0;
for (char c : s.toCharArray()) {
x |= 1 << (c - 'a');
}
for (var e : mask.entrySet()) {
int y = e.getKey(), b = e.getValue();
if ((x & y) == 0) {
ans = Math.max(ans, a * b);
}
}
mask.merge(x, a, Math::max);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int maxProduct(vector<string>& words) {
unordered_map<int, int> mask;
int ans = 0;
for (auto& s : words) {
int a = s.size();
int x = 0;
for (char& c : s) {
x |= 1 << (c - 'a');
}
for (auto& [y, b] : mask) {
if ((x & y) == 0) {
ans = max(ans, a * b);
}
}
mask[x] = max(mask[x], a);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func maxProduct(words []string) (ans int) {
mask := map[int]int{}
for _, s := range words {
a := len(s)
x := 0
for _, c := range s {
x |= 1 << (c - 'a')
}
for y, b := range mask {
if x&y == 0 {
ans = max(ans, a*b)
}
}
mask[x] = max(mask[x], a)
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| function maxProduct(words: string[]): number {
const mask: Map<number, number> = new Map();
let ans = 0;
for (const s of words) {
const a = s.length;
let x = 0;
for (const c of s) {
x |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
}
for (const [y, b] of mask.entries()) {
if ((x & y) === 0) {
ans = Math.max(ans, a * b);
}
}
mask.set(x, Math.max(mask.get(x) || 0, a));
}
return ans;
}
|
