aboutsummaryrefslogtreecommitdiff
path: root/max_product_word_len.cpp
blob: e119ea12e13a7763e4e9644f12aca37a991865b1 (plain)
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
26
27
28
29
30
31
#include "leetcode.h"

class Solution {
public:
  int maxProduct(vector<string> &words) {
    int n = words.size(), ans = 0;
    vector<bitset<26>> chars(n);
    for (int i = 0; i < n; i++) {
      for (auto &ch : words[i])
        chars[i][ch - 'a'] = 1;
      for (int j = 0; j < i; j++)
        if (!helper(chars[i], chars[j]))
          ans = max(ans, words[i].size() * words[j].size());
    }
    return ans;
  }

private:
  bool helper(bitset<26> &a, bitset<26> &b) {
    for (int i = 0; i < 26; i++)
      if (a[i] && b[i])
        return true;
    return false;
  }
};

int main() {
  Solution obj;
  vector<string> words = {"abcw", "baz", "foo", "bar", "xtfn", "abcdef"};
  cout << obj.maxProduct(words);
}