查找對不重複的字母串的擁有最長的產品

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，只比較排序的不同字母表示法。使用兩個索引（簡化形式）運行這兩個索引很容易，增加較低值的索引並檢查索引是否指向不等於字母。再次，這是不變的時間。