Given a dictionary of words, how can we efficiently find a pair words s.t. they don't have characters in common and sum of their length is maximum?

For example:
S = { "abc", "cde", "f", "efh"}.
Here the pair satisfying the property mentioned in problem will be ("abc", "efh").

两个方法：

1. bitmask:

把这个word转换成int (比如a->bit0, b->bit1, ...), 如果超过32个字符，可以用int64. 并且对每一个int，记录它的最大长度。比如aaab和ab都是0x03，但是长度不一样。

可以用std::map<int, int>，前一个int代表word转换后的值，后一个int代表这些有共同字符的words的最大长度。设word总数有N，则空间需要为O(N)。

然后对每一个int，跟其他的int进行bits AND操作，如果没有重复的字符，则结果是0，同时得到它们的长度和，跟最大长度和比较。

这样时间复杂度是O(n^2)

[还可以对pair按照它们总长度进行排序，然后先处理最长的pair，如果有一pair结果为0，则不需要再处理剩下的pair]

2. bitmask+DP

设不同的字符总数为M。同样把字符串当int处理，只不过需要空间O(2^M)。vector<int> list(2^M, 0)。然后转换word成int，同样list[i]的值代表最大长度。

不同的是list[i]代表的是所有由i包含的字符组成的任意字符串的最大长度。比如i代表ABC, 则list[i]代表(A, B, C, AB, AC, BC, ABC)这些字符串的长度的最大值，而不仅仅是ABC（这一点跟上一个方法不同）.

可以用DP方法求的整个list的值。

设i的二进制是1001001.

list[i] = max(list[i], list[bin:1001], list[bin:1000001], list[bin:1001000], list[1], list[1000000], list[1000])。

如果i不是dict里的word，则初值为0，否则初值同方法一。

因为跟i比较的都是比i小的值，所以可以用DP方法求。

需要空间O(2^M)，需要时间O(M*2^M)，因为每个值都需要比较M次。

最后一步，对任何word，设其值为k，得到它的最大长度是m(k)，对k取M位的bit NOT，得到另外一个值k'，得到他的最大长度为m(k')，则这个word的最大长度和是m(k)+m(k'). 依次计算则得到最大值。

需要时间O(N*wordlength).

秒客网