Leetcode: Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Understand the problem:
The problem is a little bit ambiguous.  The two words used to calculate the product of length must not share any common characters. e.g. word1 = abc, word2 = bcd, the product is 0 not 1, because they share common chars. 

The most straight-forward way to solve this problem is to pick up any two words, and check if they have common characters. If not, then calculate the maximum product of the length. 

Now let's analyze the complexity in time. Suppose the number of words is n, and average word length is m. So the time complexity for the  brute-force solution is O(n^2 * m). 

A better approach using bit manipulation:
Now let's think can we reduce the time complexity when we check the intersection of two words? 

Since each word contains 26 characters in lower case only. We can use a bit map to encode the string. Since we only need 26 bits for a word, it is enough to use an integer to encode a string. 

Code (Java):

public class Solution {
    public int maxProduct(String[] words) {
        if (words == null || words.length <= 1) {
            return 0;
        }
        
        int n = words.length;
        int[] encodedWords = new int[n];
        
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                char c = word.charAt(j);
                encodedWords[i] |= (1 << (c - 'a'));
            }
        }
        
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((encodedWords[i] & encodedWords[j]) == 0) {
                    maxLen = Math.max(maxLen, 
                        words[i].length() * words[j].length());
                }
            }
        }
        
        return maxLen;
    }
}

Analysis:
Compared to the brute force solution, the time complexity of the bit solution is O(26 * n^2), which is O(n^2). If m >> 26, the bit solution is better. 

Leetcode: Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

如果对所有元素进行异或操作，最后剩余的结果是出现次数为1次的两个数的异或结果，此时无法直接得到这两个数具体的值。但是，因为这两个数一定是不同的，所以最终异或的值至少有一个位为1。我们可以找出异或结果中第一个值为1的位，然后根据该位的值是否为1，将数组中的每一个数，分成两个部分。这样每个部分，就可以采用Sing number I中的方法得到只出现一次的数。

Code (Java):

public class Solution {
    public int[] singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        
        int xor = 0;
        
        // Step 1: calculate the xor for all numbers
        // So the result is the xor of the two single numbers
        for (int num : nums) {
            xor ^= num;
        }
        
        // Step 2: find the first bit 1 from right
        int mask = 1;
        while ((mask & xor) == 0) {
            mask = mask << 1;
        }
        
        int xor1 = 0;
        int xor2 = 0;
        
        for (int num : nums) {
            if ((num & mask) == 0) {
                xor1 ^= num;
            } else {
                xor2 ^= num;
            }
        }
        
        int[] result = new int[]{xor1, xor2};
        
        return result;
    }
}

Leetcode: Power of Two

Given an integer, write a function to determine if it is a power of two.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Understand the problem:
The problem is a bit manipulation problem. 

The basic idea is to bit & with mask 1, and count the number of 1s. Then shift the n to the right until n is 0. If n is power of 2, the number of 1 should be equal to 1. 

Code (Java):

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        
        int count = 0;
        
        while (n > 0) {
            count += (n & 1);
            n = n >> 1;
        }
        
        return count == 1;
    }
}

Another one-line solution:
A number is power of 2 is equalvent to if n & (n - 1) == 0. 

Code (Java):

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        
        return (n & (n - 1)) == 0;
    }
}

Leetcode: Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

Understand the problem:
We could take several examples, e.g. 5 6 7
101
110
111
-------
100

We could find out that the trick of the problem is when compare bit-by-bit for each number, once they are the same, e.g. bit 1 for the most significant bit, they start to be the same. 

9 10 11 12
1001
1010
1011
1100
---------
1000

So the solution is shift both m and n to the right until they are the equal, count the number of steps it shifted. Then shift m left to the number of steps. 

Code (Java):

public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        
        while (m != n) {
            shift++;
            m = m >> 1;
            n = n >> 1;
        }
        
        return m << shift;
    }
}

Leetcode: Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Understand the problem:
The questions is quite easy to address. Each time we get the least significant bit and check if it is 1. Then shift the number to the right by 1 until 32 times. 

Code (Java):

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result += n & 1;
            n = n >> 1;
        }
        
        return result;
    }
}

Leetcode: Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

Understand the problem:
We could get the least significant bit each time and append to the new result. 
e.g. 11100, we get 0 0 1 1 1, and append to the new result from right to left as well.

Code (Java):

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n = (n >> 1);
        }
        
        return result;
    }
}

Leetcode: Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Naive Solution:
Use a hash map to contain the number of each element. Then iterate the map. 

Code (Java):

public class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        
        int len = nums.length;
        
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            int key = (int) pair.getKey();
            int value = (int) pair.getValue();
            
            if (value > len / 2) {
                return key;
            }
        }
        
        return 0;
    }
}

A constant-space solution:
Since the major element must occur more than n/2 times. We could compare each pair numbers, if not the same, we eliminate it. The left number must be the majority number. 

Code (Java):

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int result = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                result = nums[i];
                count = 1;
            } else if (nums[i] == result) {
                count++;
            } else {
                count--;
            }
        }
        
        return result;
    }
}

Leetcode: Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Understand the problem:
The naive approach is to use a sliding window, with size of 10. Put the visited string into a map. If the substring is visited again, add into the result. 

Code (Java):

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() < 10) {
            return result;
        }
        
        Map<String, Integer> map = new HashMap<String, Integer>();
        
        int lo = 0;
        int hi = 9;
        
        while (hi < s.length()) {
            String substring = s.substring(lo, hi + 1);
            if (map.containsKey(substring) && map.get(substring) == 1) {
                result.add(substring);
                map.put(substring, map.get(substring) + 1);
            } else {
                map.put(substring, 1);
            }
            
            lo++;
            hi++;
        }
        
        return result;
    }
}

The code got memory limit exceeding error. Why? Because the space complexity is O(10 * n). We need to think of a better approach with less memory cost. 

Use bit manipulation:
Since the string contains only 4 characters, we could encode the characters using 2 bits each, i.e, 
'A' -- 00
'C' -- 01
'G' -- 10
'T'  -- 11
And since the length of the substring is only 10 characters, the total number of bits needed are only 20. Therefore we could encode a string into a integer. 

Code (Java):

public class Solution {
    private Map<Character, Integer> codingMap = new HashMap<Character, Integer>();
    
    private int encode(String s) {
        int value = 0;
        for (int i = 0; i < s.length(); i++) {
            value = (value << 2) + codingMap.get(s.charAt(i));
        }
        
        return value;
    }
    
    private void fill() {
        codingMap.put('A', 0);
        codingMap.put('C', 1);
        codingMap.put('G', 2);
        codingMap.put('T', 3);
    }
    
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() < 10) {
            return result;
        }
        
        fill();
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        int lo = 0;
        int hi = 9;
        
        while (hi < s.length()) {
            String substring = s.substring(lo, hi + 1);
            int hashCode = encode(substring);
            if (map.containsKey(hashCode) && map.get(hashCode) == 1) {
                result.add(substring);
                map.put(hashCode, map.get(hashCode) + 1);
            } else {
                if (!map.containsKey(hashCode)) {
                    map.put(hashCode, 1);
                } else {
                    map.put(hashCode, map.get(hashCode) + 1);
                }
            }
            
            lo++;
            hi++;
        }
        
        return result;
    }
}

Analysis:
Now let's analyze the space cost. Since in Java, each character takes 2 bytes. For the previous solution using string, a 10-character substring takes 20 byte. For using the integer, which takes only 4 bytes. So the new solution saves the memory by 1/5. 

Leetcode: Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Understand the problem:
The problem is similar to the Single Number I, except that each number appears three times. Note that the problem asks for linear time complexity and constant space. 

Naive Solution:
The naive solution could use a hash table. It uses hash table instead of hash set because we want store the number of occurrence of each number. For each number if it is the first or second occurrences, we update the second value. For the third times, we remove that entry. So the only number in hash table is the one we are looking for.

Code (Java):

public class Solution {
    public int singleNumber(int[] A) {
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        int num = 0;
        
        for (int i = 0; i < A.length; i++) {
            if (!hashMap.containsKey(A[i])) {
                hashMap.put(A[i], 1);
            } else if (hashMap.get(A[i]) == 1) {
                hashMap.put(A[i], 2);
            } else if (hashMap.get(A[i]) == 2) {
                hashMap.remove(A[i]);
            }
        }
        Set<Integer> set = new HashSet<Integer>();
        set = hashMap.keySet();
        
        for (Integer n : set) {
            num = n;
        }
        return num;
    }
}

  
Discussion:
We see that the solution has O(n) in time, however O(n) in space. So we need to find out another way to solve it using constant space.

A Better Solution:

public class Solution {
    public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int[] bits = new int[32];
        
        // step 1: calcuate the number of bits for each number
        for (int num : nums) {
            int mask = 1;
            for (int i = 31; i >= 0; i--) {
                if ((num & mask) != 0) {
                    bits[i]++;
                }
                mask = (mask << 1);
            }
        }
        
        // step 2: find out the single number
        int result = 0;
        for (int i = 0; i < 32; i++) {
            bits[i] %= 3;
            if (bits[i] == 1) {
                result += 1;
            }
            
            if (i == 31) {
                break;
            }
            
            result = (result << 1);
        }
        
        return result;
    }
}

Leetcode: Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Understand the Problem:

As described in the problem, given an array of integers, every element appears twice except for one. The problem asks for finding the single one. Furthermore, the problem asks for linear time complexity and constant space complexity. 

Naive Approach:

As is described in the problem, each element appears twice except for one. So a straight-forward solution could use a hash set. For the element first encountered, we add it into the set. For the second met, we remove it. As a result, after iterating all elements of the array, the hashset only contains one element, which is the one we are looking for.

Code (Java):

public class Solution {
    public int singleNumber(int[] A) {
        HashSet<Integer> hashset = new HashSet<Integer>();
        int ret = 0;
        int len = A.length;
        
        for (int i = 0; i < len; i++) {
            if (!hashset.contains(A[i])) {
                hashset.add(A[i]);
            } else {
                hashset.remove(A[i]);
            }
        }
        
        for (Integer num : hashset) {
            ret = num;
        }
        return ret;
    }
}

Discussion:
As we can see that this approach has time complexity of O(n). However, the space complexity is O(n) as well since we used additional space. 

A better approach:
Since we are required to use constant space, we can think of using bit manipulation. We use XOR. Since x ^ x = 0. x ^ y ^ x = y. So we can use the XOR to eliminate the repeated numbers. 

Code (Java):

public class Solution {
    public int singleNumber(int[] A) {
        int num = A[0];
        
        for (int i = 1; i < A.length; i++) {
            num = num ^ A[i];
        }
        
        return num;
    }
}

Discussion:
Note that the solution utilized two properties: First of all, XOR is comm.communicative, i.e. x ^ y ^ x = x ^ x ^ y = y. Second, The solution relied on the assumption that each number appeared two times while one appears once. If this condition does not stand, the solution of using XOR does not hold.

Summary:
This post we learned a very simple problem but required tricky solution to solve it. Using bit manipulation is very subtle. If you are asked to perform an operation without using extra space, consider the bit manipulation.