查找对不重复的字母串的拥有最长的产品

Question

我碰到这个谷歌面试问题，无法找到为O更好的解决方案（N^2）

Given a list of words, find two strings S & T such that: 

a. S & T have no common character 
b. S.length() * T.length() is maximized 

我的解决办法：

//Firstly sort all the strings base on length so that longer strings are at front of list. 
sort(words.begin(), words.end()); 
//Then I have the double for loop that can break as soon as we found a pair 
for current string 
int found = words.size(); 
for(int i=0; i<min(found, words.size()-1); i++) { 
    for(int j=i+1; j<min(found, words.size()); j++) { 
     if(noSameLetter(words[i], words[j])){ 
      int product = words[i].length() * words[j].length(); 
      maxProduct = max(maxProduct, product); 
      found = j; 
      break;         
     } 
    } 
} 

noSameLetter将采取O（wordLength），我省略了它的代码。

我试图在上面的代码中尽可能地修剪，例如如果我有长度： 10，9，8，7，6，5，4，3，2，1和我已经找到了一对（10，7），我将不尝试任何一对后7.

Answer 1

你的溶液开始，更准确地，是Θ（N W），其中W¯¯是的复杂性noSameLetter。我想指出的是，有一些预处理，W = O（1），总的复杂性，预计Θ（N + ∑ _我 | W _我 |）（其中| w _i |是词的长度i）。

• 对于每个单词，找出不同字母（使用哈希表的集合，所散发出来的长度预期线性）

• 排序的不同字母（这是O（1），如字母大小是固定的）。

要实现noSameLetter，只比较排序的不同字母表示法。使用两个索引（简化形式）运行这两个索引很容易，增加较低值的索引并检查索引是否指向不等于字母。再次，这是不变的时间。