Maximal Product of Two Non-overlapping Words in a Dictionary

wordProduct.cpp

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

bitset<26> to_bits(const string& word) {
    bitset<26> ans;
    for (int i = 0; i < word.size(); i++)
        if (!ans[word[i] - 'a'])
            ans.flip(word[i] - 'a');
    return ans;
}

// Find maximum product of non-overlapping words:
int max_product(const vector<string>& words) {
    vector<bitset<26>> bitwords;
    for (int i = 0; i < words.size(); i++)
        bitwords.push_back(to_bits(words[i]));

    size_t ans = 0;
    bitset<26> bitzero(0);
    for (int i = 0; i < bitwords.size(); i++)
        for (int j = i + 1; j < bitwords.size(); j++)
            if ((bitwords[i] & bitwords[j]) == bitzero)
                ans = max(ans, words[i].size() * words[j].size());
    return ans;
}

int main() {
	// your code goes here
	vector<string> input = { "apple", "banana", "my", "peer" };
	cout << max_product(input) << endl;
	return 0;
}