Java 18ms solution, with explanation


  • 3
    A

    The idea is to have to represent each string in a binary format. We will "turn the bit on" based on it's position in the alphabets. For example, if we have a word
    "a" then its binary format would be 1, because a is the first letter in the alphabets.
    "ab" would have the binary format 11,
    "ac" would have the binary format 101,
    "d" would have the binary format 1000, because d is the forth letter in the alphabets.

    The reason why we represent them in binary is because we can do an & (i.e. AND) operations on two strings. If the result is 0 then the two words don't share any common letter, and we update uor max variable that holds the products of the two words

        public int maxProduct(String[] words) {
            int [] bitmask = new int[words.length];
            int index = 0;
            for(String w : words){
                for(int i = 0; i < w.length(); i++){
                    bitmask[index] |= 1 << w.charAt(i) - 'a';
                }
                index++;
            }
    
            int max = 0;
            for(int i = 0; i < words.length; i++){
                for(int j = i + 1; j < words.length; j++){
                    if((bitmask[i] & bitmask[j]) == 0){
                        max = Math.max(max, words[i].length() * words[j].length());
                    }
                }
            }
    
            return max;
            
        }
    
    

Log in to reply
 

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