421. Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

题目希望找到两个数的XOR最大。

求数组中两两数字的异或运算的最大值，brute force的解法是O(n ^ 2)，

怎么样才能XOR最大呢？我们从最大bit位上面看，如果有0，有1那么这位可以在答案中加上。

nums中，与mask按位与结果为0的所有数字，记为nums0

nums中，与mask按位与结果为1的所有数字，记为nums1

如果nums0与nums1其一为空，说明nums中所有数字在该二进制位同0或同1，其异或结果一定为0

如果nums0与nums1均不为空，说明nums中的数字在该位的异或值为1，令mask右移一位，再将nums0与nums1进一步划分成四部分：

nums0中，与mask按位与结果为0的所有数字，记为nums00

nums0中，与mask按位与结果为1的所有数字，记为nums01

nums1中，与mask按位与结果为0的所有数字，记为nums10

nums1中，与mask按位与结果为1的所有数字，记为nums11

分治法（Divide and Conquer）+ 位运算（Bit Manipulation）就是上面分析过程引用bookshadow的解法http://bookshadow.com/weblog/2016/10/15/leetcode-maximum-xor-of-two-numbers-in-an-array/

2.
一个比较直观的解法，用prefix Trie
对于每一个num来说，看它会不会构成最后的结果，就是看它的sibling有没有，如果有sibling，那么这位xor的结果就是1，不然xor的结果是0.对个num都做一遍，然后去取最大的值。https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie/2


3. 构造这个xor结果

example: Given [14, 11, 7, 2], which in binary are [1110, 1011, 0111, 0010].
Since the MSB is 3, I'll start from i = 3 to make it simplify.

1. i = 3, set = {1000, 0000}, max = 1000  
2. i = 2, set = {1100, 1000, 0100, 0000}, max = 1100  -> 1110 0010 或者 1100 0010 或者 1010 0100 或者 1000 0110 都可以构成1110
3. i = 1, set = {1110, 1010, 0110, 0011}, max = 1100
4. i = 0, set = {1110, 1011, 0111, 0011}, max = 1101

外循环是31～0
因此每一位的比较，我们还需要知道前边那些位，比如我们这轮儿想要知道答案有没有111X（因为我们已经知道有11XX）因此我们取出每个数前3个bit位放入set。在set中利用想要知道的结果来找另一半。（x^y = z --> x^z = y   =》 x^y =  max(理想的) --> x^max = y)）

int findMaximumXOR(vector<int>& nums) {
        int max = 0, mask = 0;
        unordered_set<int> t;
        // search from left to right, find out for each bit is there 
        // two numbers that has different value
        for (int i = 31; i >= 0; i--){
            // mask contains the bits considered so far
            mask |= (1 << i);
            t.clear();
            // store prefix of all number with right i bits discarded
            for (int n: nums){
                t.insert(mask & n);
            }
            
            // now find out if there are two prefix with different i-th bit
            // if there is, the new max should be current max with one 1 bit at i-th position, which is candidate
            // and the two prefix, say A and B, satisfies:
            // A ^ B = candidate
            // so we also have A ^ candidate = B or B ^ candidate = A
            // thus we can use this method to find out if such A and B exists in the set 
            int candidate = max | (1<<i);
            for (int prefix : t){
                if (t.find(prefix ^ candidate) != t.end()){
                    max = candidate;
                    break;
                }
                
            }
        }
        return max;
    }

https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap/7

395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

本来想用dp做。。。
dp[i] 存包括strs[i]的最长<Length,  Map<Character,Integer>> 但是map里边应该只存包含length结果的那些character的map 而不是所有的。

没有简化问题。。。

http://blog.csdn.net/mebiuw/article/details/52449892

“这个不是一般的DP或者暴力的解决方式，要用一下递归：

1、统计每个字母【只有小写】出现的次数 
2、找出不合法的字符【出现了，但是次数不够K】 
3、如果没有任何不合法字符，那么返回串的长度 

4、如果有不合法的字符，那么将这个串按照本轮不合法的字符位置切开（一个不合法的字符就切一刀），切开后的每一个子串递归执行1，取最长的返回”

  public int longestSubstring(String s, int k) {  
     if(s.length() < k) return 0 ;  
     HashMap<Character,Integer>count = new HashMap<>();  
     Set<Character> set = new HashSet<>();  
     for(int i = 0; i < s.length(); i++){  
       char c = s.charAt(i);  
       count.putIfAbsent(c,0);  
       count.put(c,count.get(c)+1);  
       if(count.get(c) >= k)  
         set.remove(c);  
       else   
         set.add(c);  
     }      
     if(set.size() == 0) return s.length();  
     List<String> strs = new ArrayList<>();  
     int lo = 0;    int max = 0;  
     for(int i = 0; i < s.length(); i++){  
       if(set.contains(s.charAt(i))){  
         if(lo!=i)  
           max = Math.max(max, longestSubstring(s.substring(lo,i),k));  
         lo = i+1;  
       }  
     }  
     if(lo!= s.length())   
       max = Math.max(max, longestSubstring(s.substring(lo,s.length()),k));  
     return max;  
   }