Maximum Product of Word Lengths - Medium - L
Published:
Question
- https://leetcode.com/problems/maximum-product-of-word-lengths/
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.
Approach
- Frequency approach
- Bitwise AND **
Represent the strings in form of binary numbers. (i.e. ‘a’ will represent 1st bit , b will represent 2nd bit , and so on.) for example : a - 1, b- 10, c - 100, ab- 11, acd - 1101 if there is redundancy in characters (ex - “aabb” ), then only consider one repetation for example : “aabb” - 11 and “ab” and “aab” are also consider 11.
Then check for every pair : if bitwise & of these numbers is 0, then find maximum product of their lengths.
Example : [“a”, “abb”, “cd”, “abc”, “ade”] Converting into binary form: [1, 3, 12, 7, 25] i.e-> [“1”, “11”, “1100”, “111”, “11001”] Now since bitwise & of 1 and 12 is 0 , and Product of string length= 12 =2 3 and 12 is 0 , and Produnt of string length = 32 =6 Therefore, our ans is max(2,6) = 6
class Solution {
public:
int maxProduct(vector<string>& words) {
int n=words.size();
vector<long>v;
for(string s:words){
long k=0;
for(char ch:s){
long bit=(ch-'a');
if(!((k>>bit)&1))k+=1<<bit; // checks if bit is not set in k (i.e. 0) then add 1<<bit to k;
}
v.push_back(k);
}
// for(auto x:v)cout<<x<<" ";
int ans=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if((v[i]&v[j])==0)ans=max(ans,(int)(words[i].length()*words[j].length()));
}
}
return ans;
}
};
Solution
class Solution {
public:
int maxProduct(vector<string>& words) {
vector<vector<int>> v;
int n = words.size();
for(int i=0; i<n; i++) {
vector<int> freq(26,0);
int t = words[i].size();
for(int j=0; j<t; j++) {
freq[words[i][j]-'a']++;
}
v.push_back(freq);
}
int ans = 0;
for(int i=0; i<n; i++) {
for(int j=i; j<n; j++) {
int fl = 0;
for(int k=0; k<26; k++) {
if(v[i][k]==0 && v[j][k]==0) {
continue;
}
if(v[i][k]==0 || v[j][k]==0) {
continue;
} else {
fl = 1;
}
}
if (fl==0) {
int temp = words[i].size()*words[j].size();
if (temp > ans) {
ans = temp;
}
}
}
}
return ans;
}
};