# Possible sub-quadratic bound? O(N + 2^26)?

• What sub-quadratic bound are we expected to achieve? So far, I have an O(N + 2^26)-time algorithm using bitmask-DP, where N is the sum of all string lengths. Unfortunately, an array of size 2^26 costs 256MB memory, which exceeds the heap size limit.

• Neither O(n^2) nor O(n + 2^26) is possible. So far, yular is the only one stating their complexity correctly.

• Assume the total length of all strings is N, then O(N+2^26) can be achieved.

• I have updated my statement, thank you for your suggestion.

• For those interested I have coded up a O(n*k*2^26) solution below, where k is the length of the longest string. The only problem is that it gives a TLE. I would be interested if someone could make this idea work in the given time limit.

``````public class Solution {
public int maxProduct(String[] words) {
HashMap<Integer, Double> table = new HashMap<Integer, Double>();
table.put(0, -1.0);

for(String str : words){
if(str.equals(""))
continue;

int sig = giveSigniture(str);
writeTable(sig, Math.log(str.length()), table);
}

return (int)Math.round(Math.exp(table.get(0)));
}

/* Give a bit signiture to each word.
* Have bit i set to 1 if the i'th letter in the alphabet appears in the word and 0 otherwise
*/
public int giveSigniture(String str){
int sig = 0;
for(int i = str.length()-1; i >= 0; --i){
int mask = 1<<(str.charAt(i) - 'a');

}
return sig;
}

public static void writeTable(int sig, double value, HashMap<Integer, Double> table){
if(!table.containsKey(sig) || value > table.get(sig))
table.put(sig, value);

ArrayList<Integer> past = new ArrayList<Integer>();
ArrayList<Integer> next = new ArrayList<Integer>();
ArrayList<Integer> temp;

int newSig = (~sig)&0x3FFFFFF; //This gives the largers set of letters that are not contained in the current word.

double max = table.get(0);
if(table.containsKey(newSig))
max = Math.max(max, value + table.get(newSig));

for(int i = 0; i < 26; ++i){

for(int num: past){
int num2 = num&(~mask); //Make the i'th bit set to 0.

if(num2 > 0 && num2 != num)

//See if there are any words so far that have no leeters in common with the current word
if(num2 > 0 && table.containsKey(num2))
max = Math.max(max, value + table.get(num2));
}
temp = past;
past = next;
next = temp;
next.clear();

}
table.put(0, max);
}
}``````

• This post is deleted!

• Well O(mn+n*2^alpha) is the run time if m is the average length of all the strings. I think in most applications the length of any given string will be less then 36 in which case the running time would O(n*2^alpha).

• Your asterisks disappeared and made text italic, you can backslash-escape them to prevent that.

Why do you say "less then 36", is it because you're kevin36? :-)

• @Stefan well actually that 36 in this case is just a funny coincidence. I remember reading about how c++ STL string uses a quick optimization for short strings with length less then 24-36 chars in length.

So I figured that the assumption the strings length are of bounded length.

• Here's a solution that runs in O(mn + alpha * 2^alpha) time.

(n = number of words in dictionary, m = longest dictionary word length, alpha = alphabet size)

It's based off of Michal Forisek's solution here: http://qr.ae/RbidEz

It doesn't pass the judge since the judge runs on smaller dictionaries.

``````public class Solution {
public static int maxProduct(String[] dictionary) {
int numWords = dictionary.length;
String alphabet = "abcdefghijklmnopqrstuvwxyz";
char[] alphabetArr = alphabet.toCharArray();
int alphabetSize = alphabetArr.length;
int[] alphabetIndices = new int[256];
int numSubsets = (int)Math.pow(2, alphabetSize);
String[] bestWordsExact = new String[numSubsets];
String[] bestWordsAtMost = new String[numSubsets];
String[] maxWords = new String[2];

for (int i = 0; i < alphabetSize; i++) {
int currentChar = alphabetArr[i];
alphabetIndices[currentChar] = i;
}

for (int i = 0; i < numWords; i++) {
String currentWord = dictionary[i];
char[] currentWordArr = currentWord.toCharArray();
int wordLength = currentWordArr.length;
int subsetIndex = 0;

for (int j = 0; j < wordLength; j++) {
char currentChar = currentWordArr[j];
int alphabetIndex = alphabetIndices[currentChar];
subsetIndex |= (1 << alphabetIndex);
}

String existingWord = bestWordsExact[subsetIndex];

if (existingWord == null || existingWord.length() < currentWord.length()) {
bestWordsExact[subsetIndex] = currentWord;
}
}

for (int i = 0; i < numSubsets; i++) {
int maxLength = -1;
String maxWord = "";
String exactWord = bestWordsExact[i];

if (exactWord != null) {
int exactWordLength = exactWord.length();

if (exactWordLength > maxLength) {
maxLength = exactWordLength;
maxWord = exactWord;
}
}

for (int j = 0; j < alphabetSize; j++) {
int mask = ~(1 << j); // Build up 0111111...11
int subsetIndex = i & mask;
String atMostWord = bestWordsAtMost[subsetIndex];

if (atMostWord != null) {
int atMostWordLength = atMostWord.length();

if (atMostWordLength > maxLength) {
maxLength = atMostWordLength;
maxWord = atMostWord;
}
}
}

bestWordsAtMost[i] = maxWord;
}

int maxCombinedLength = -1;

for (int i = 0; i < numWords; i++) {
String currentWord = dictionary[i];
char[] currentWordArr = currentWord.toCharArray();
int currentWordLength = currentWordArr.length;
int subsetIndexNotIncluded = 0;

for (int j = 0; j < alphabetSize; j++) {
subsetIndexNotIncluded |= (1 << j);
}

for (int j = 0; j < currentWordLength; j++) {
char currentChar = currentWordArr[j];
int alphabetIndex = alphabetIndices[currentChar];
subsetIndexNotIncluded &= ~(1 << alphabetIndex);
}

String bestMatchWord = bestWordsAtMost[subsetIndexNotIncluded];
int bestMatchWordLength = bestMatchWord.length();
int totalLength = currentWordLength * bestMatchWordLength;

if (totalLength > maxCombinedLength && bestMatchWordLength != 0) {
maxCombinedLength = totalLength;
maxWords[0] = currentWord;
maxWords[1] = bestMatchWord;
}
}

return maxWords[0].length() * maxWords[1].length();
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.