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


  • 1
    L

    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.


  • 0

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


  • 0
    L

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


  • 0
    L

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


  • 0
    K

    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');
                
                if((mask&sig) == 0)
                    sig |= mask;
            }
            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.
            past.add(newSig);
    
            double max = table.get(0);
            if(table.containsKey(newSig))
                max = Math.max(max, value + table.get(newSig));
    
            for(int i = 0; i < 26; ++i){
                int mask = 1<<i;
                
                for(int num: past){
                    int num2 = num&(~mask); //Make the i'th bit set to 0.
    
                    next.add(num);
                    if(num2 > 0 && num2 != num)
                        next.add(num2);
    
                    //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);
        }
    }

  • 0
    This post is deleted!

  • 0
    K

    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).


  • 1

    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? :-)


  • 0
    K

    @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.


  • 0
    K

    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();
        }
    }

Log in to reply
 

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