Hash table questions: https://leetcode.com/tag/hash-table/

1. Hash Table

1.1 Sliding Window Substring

LC3: Longest substring without repeating characters

Given a string, find the length of the longest substring without repeating characters.

two-pointers: 'i' scans the whole string, 'j' points to the start of each no-repeat window
whenever we find a repeated char, we move 'j' to the right of last occurrence index (if 'j' falls behind the new pos before movement).
we keep putting chars into the map, updating the index, and counting the non-repeat length.

 
int lengthOfLongestString(string s) {
  unordered_map<char, int> mp;
  int maxLen = 0;
  for(int j=0, i=0; i<n; ++i) {
    char c = s[i];
    if(mp.find(c) != mp.end()) {
      j = std::max(j, mp[c]+1);
    }
    mp[c] = i;
    maxLen = std::max(maxLen, i-j+1);
  }//--for
  return maxLen;
}

LC159: Longest substring with at most two distinct characters

LC340: Longest substring with at most K distinct characters

Given a string, find the length of the longest substring T that contains at most K distinct characters.

when map size is over 2, i.e., 3 or more chars have been found, then move pointer 'j' until K chars are there.

 
int lengthOfLongestSubstringTwoDistinct(string s, int K) {
  unordered_map<char, int> mp;
  int maxLen = 0;
  for(int j=0, i=0; i<n; ++i) {
    char c = s[j];
    ++ mp[c];
    while(mp.size()>K) {
      if(--mp[s[j]]==0) mp.erase(s[j]);
      ++ j;
    }
    maxLen = std::max(maxLen, i-j+1);
  }//--for
  return maxLen;
}

LC424: Longest repeating character replacement

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

The problem is similar to longest substring with most K distinct chars. But this time, the constraint is we can only have most K characters that is different with the most frequent character in the substring. 

 
int characterReplacement(string s, int k) {
  unordered_map<char, int> mp;
  int maxLen = 0, freq = 0;
        
  for(int j=0, i=0; i<n; ++i) {
    char c = s[i];
    freq = std::max(freq, ++mp[c]);
    while((i-j+1) - freq > k) {
      if(--mp[s[j]]==0) mp.erase(s[j]);
      ++ j;
    }
    maxLen = std::max(maxLen, i-j+1);
  }//--for
  return maxLen;
}

LC395: 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.

first record counts of every character in a hashmap
then, locate the first character that appear less than k times in the string. this character is definitely not included in the result, and that separates the string into two parts.
keep doing this recursively and the maximum of the left/right part is the answer.

 
class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.length();
        if(n==0 || n<k) return 0;
        
        vector<int> mp(26, 0);
​
        for(int i=0; i<n; ++i) {
            int cind = s[i] - 'a';
            ++ mp[cind];                //count appearance of each char
        }//--for
        
        int idx = 0;
        while(idx<n && mp[s[idx]-'a']>=k) ++ idx;
        if(idx == n) return n;
        
        int left = longestSubstring(s.substr(0, idx), k);
        int right = longestSubstring(s.substr(idx+1), k);
        
        return std::max(left, right);
    }
};

LC438: Find all anagrams in a string

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

 
vector<int> findAnagrams(string s, string p) {
  int n = s.length(), m = p.length();
  if(n < m) return {};
  
  vector<int> rst;
  vector<int> pmap(26,0), wmap(26,0);       //'p' map and sliding window map
  for(auto c : p) ++ pmap[c-'a'];           //init pmap
  for(int i=0; i<m; ++i) ++ wmap[s[i]-'a'];  //init wmap
  if(pmap == wmap) rst.push_back(0);
  for(int i=m; i<n; ++i){
    char c = s[i];
    ++ wmap[c-'a'];
    -- wmap[s[i-m]-'a'];
    if(pmap == wmap) rst.push_back(i-m+1);
  }//--for
  return rst;
}

LC76: Minimum window substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

1) build a map<char, int> for string T, count the map size, M
2) use two pointers to search string S: whenever we find a char in T, we place/update the map, and only count when it is new or times less than that in T map
3) when count reaches  M, we have found a window holding all chars in T, and now we test to shrink the left to maintain the meet condition (when stop, leftmost char must be an effective one in T)
4) calculate the length and compare against min
5) move left pointer forward, decrease count, and repeat the above steps

 
string findMinWindow(string S, string T) {
  if(S.length() < T.length()) return "";
  unordered_map<char, int> mp;
  for(auto c : T) ++ mp[c];
  
  unordered_map<char, int> seen;
  int count = 0, minLen = INT_MAX, minStart = 0;
  for(int j=0, i=0; i<S.length(); ++i) {
    char c = s[i];
    if(mp.find(c) != mp.end()) {
      ++ seen[c];
      if(seen[c] <= mp[c]) ++ count;
    } 
    if(count == mp.size()) {
      while(mp.find(s[j])==mp.end() || seen[s[j]]>mp[s[j]]) {
        if(seen.find(s[j])!=seen.end()) --seen[s[j]];
        ++ j;
      }
    }
    //now 'j' points to an effective char
    int curLen = i-j+1;
    if(curLen < minLen) {
      minLen = curLen;
      minStart = j;
    }
    ++ j;
    -- count;
    -- seen[s[j]];
  }//--for
  return minLen==INT_MAX ? "" : s.substr(minStart, minLen);
}

LC30: Substring with concatenation of all words

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Each time look forward total 'words' length, if all matches, record the index and move one step forward;
if certain word matches more times, or some word doesn't match, break and test next sequence

 
vector<int> findSubstring(string s, vector<string>& words) {
  int nw = words.size(); int len = words[0].length();
  if(s.length() < nw*len) return {};
  unordered_map<string, int> dict;
  for(auto wd : words) ++ dict[wd];
  
  unordered_map<string, int> seen;
  vector<int> rst;
  for(int i=0; i<s.length()-nw*len+1; ++i) {
    seen.clear();
    int j = 0;
    for(; j<nw; ++j) {
      string wd = s.substr(i+j*len, len);   //extract the word
      if(dict.find(wd) == dict.end()) break;
      ++ seen[wd];
      if(seen[wd] > dict[wd]) break;
    }//--for
    if(j == nw) rst.push_back(i);
  }//--for
  return rst;
}

1.2 Sliding Window

LC239: Contains duplicate II

maintain a set containing unique values from nums[i-k] to nums[i-1]
if(nums[i]) is in set s, then return true; ow, update the set

 
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();
        if(n == 0) return false;
        if(n <= k) k = n-1;
        
        unordered_set<int> set;
        for(int i=0; i<nums.size(); ++i) {
            if(i > k) set.erase(nums[i-k-1]);
            if(set.find(nums[i]) != set.end()) return true;
            set.insert(nums[i]);
        }//--for
        
        return false;
    }

LC220: Contains duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Using a set to keep the k+1-lenght array, which all elements are distinct. Before the container's size reached k+1, we just find the first elment that is not less than [nums[i]-t] and judge the element's value whether it is less than [nums[i]+t].

$-t\le x-nums[i]\le t$ <==> $x\ge nums[i]-t\;\&\&\; x-nums[i]\le t$

 
        set<long long int> set;
        for(int i=0; i<n; ++i) {
            if(i > k) set.erase(nums[i-k-1]);
            
            auto pos = set.lower_bound((long long)nums[i]-t);       //time: log(k)
            if(pos != set.end() && (long long)*pos-(long long)nums[i]<=t) return true;
            
            set.insert((long long)nums[i]);
        }//--for
        
        return false;
//see: http://www.cnblogs.com/grandyang/p/4545261.html

LC239: Sliding window maximum

LC480: Sliding window median

1.3 Strings

LC49: Group anagrams

Given an array of strings, group anagrams together.

 
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n = strs.size();
        std::vector<std::vector<std::string>> rst;
        if(n == 0) return rst;
        
        std::unordered_map<std::string, int> map;       //hash map
        for(int ii=0; ii<n; ++ii){
            std::string word = strs[ii];
            std::sort(word.begin(), word.end());
            if(map.find(word)==map.end()) {             //first see
                int size = map.size();
                map[word] = size; //map.size();                 //key=word, value=loc in vector
                rst.push_back({strs[ii]});
            } else {                                    //already appeared
                int pos = map[word];
                rst[pos].push_back(strs[ii]);
            }
        }//-for
        
        return rst;
    }
};

LC336: Palindrome pairs

LC291: Word pattern II

LC244: Shortest word distance II

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

LC249: Group shifted strings

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

LC358: Rearrange string k distance apart

Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

HashMap + Max Heap + Greedy
We work on chars with highest frequency, and put them k-distance apart. And, in between we place the remaining (k-1) chars.
1) build the mapping between the char and frequency
2) feed to mapping info to max heap, and pick up the most frequent one to place; we know that the chars cannot be adjacent, and thus we remove the char from the heap and save it somewhere else, then we pick up the next (k-1) chars in such fashion. After the round, i.e., placing k chars, we place the removed ones back to the heap, and repeat the above steps;
3) the rearrangment is impossible if the heap becomes empty, as we have no way to make them k-distance apart.

 
string rearrangeString(string s, int k) {
  int len = s.length();
  if(k==0) return s; 
  //count char frequncy
  unordered_map<char, int> mp;
  for(auto c : s) ++mp[c];
  //place into heap
  using T = std::pair<int, char>;
  priority_queue<T> pq;
  for(auto it=mp.begin(); it!=mp.end(); ++it)
    pq.push({it->second, it->first});
  //greedy to put
  string rst = "";
  while(!pq.empty()) {
    vector<T> cache;
    int cnt = std::min(len, k);
    for(int i=0; i<cnt; ++i) {
      if(pq.empty()) return "";
      T item = pq.top(); pq.pop();
      rst += item.second;
      if(--item.first > 0)
        cache.push_back(item);
      -- len;
    }//--for
    for(auto item : cache) pq.push(item);
  }//--while
  return rst;
}
//see: http://juneend.blogspot.com/2016/07/358-rearrange-string-k-distance-apart.html
//see: http://www.cnblogs.com/grandyang/p/5586009.html

Task schedule

-Task schedule I

 
string taskSchedule(vector<int>& tasks, int cooldown){
  string rst = "";
  int cycle = 0;
  unordered_map<int, int> mp; //key=taskID, value=last schedule time
  for(int i=0; i<tasks.size(); ) {
    int task = tasks[i];
    if(mp.find(task)==mp.end() || cycle>=mp[task]+cooldown) {
      rst += std::to_string(task);
      mp[task] = cycle;
      ++ i;
    } else {
      rst += "-";
    }
    ++ cycle;
  }//--for
}

-Task schedule II

 
int taskSchedule(vector<int>& tasks, int cooldown){
  int time = 0;
  unordered_map<int, int> mp;   //key=taskID, value=last schedule time
  for(int i=0; i<tasks.size(); ++i) {
    int task = tasks[i];
    if(mp.find(task)!=mp.end() && cycle<=mp[task]+cooldown){
      int idlecycles = mp[task]+cooldown - cycle;
      time += idlecycles;
    }
    ++ time;
    mp[task] = time;
  }//--for
}

-Task schedule III

Given a sequence of tasks like A B C (means 3 different tasks), and a cold time, which means you need to wait for that much time to start next [same] task, now find the sequence of tasks such that all tasks are finished in minimum time.

Input: string, n, e.g., AAABBB, 2

Output: AB_AB_AB ("_" represents do nothing and wait)

 
int cnt = k; //std::min(len, k);
//if(pq.empty()) return "";
if(pq.empty()) {rst+="-"; continue;}

1.4 Geometry and Math

LC447: Number of bloomerangs

LC356: Line reflection

LC149: Max points on a line

LC166: Fraction to recurring decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

http://blog.csdn.net/ljiabin/article/details/42025037

LC380: Insert delete getrandom O(1)

Design a data structure that supports all following operations in average O(1) time.

LC381: Insert delete get random O(1) - Duplicates allowed

Design a data structure that supports all following operations in average O(1) time.

 
    unordered_map<int,priority_queue<int>> mp;       //cannot use 'vector<int>' here
    vector<int> data;
//see: https://discuss.leetcode.com/topic/53687/c-solution-using-map-and-vector-with-detailed-explanation/2
//see: http://www.cnblogs.com/grandyang/p/5756148.html

1.5 Others

LC508: Most frequent subtree sum

Given the root of a tree, you are asked to find the most frequent subtree sum. 

 
        unordered_map<int,int> mp;
        getSum(root, mp);
        
        unordered_map<int, vector<int>> cntMap;
        int maxCnt = 0;
        for(auto it=mp.begin(); it!=mp.end(); ++it) {
            int val = it->second;
            maxCnt = std::max(val, maxCnt);
            cntMap[val].push_back(it->first);
        }//--for
        return cntMap[maxCnt];

2. Matrix

LC42: Trapping rain water

LC11: Container with most water

LC407: Trapping rain water II

LC84: Largest rectangle in histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

http://www.cnblogs.com/boring09/p/4231906.html

LC221: Maximal square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

 
        int maxSide = 0;
​
        //topmost row
        for(int j=0; j<c; ++j) {
            dp[0][j] = matrix[0][j] - '0';
            maxSide = std::max(maxSide, dp[0][j]);
        }
        //leftmost col
        for(int i=0; i<r; ++i) {
            dp[i][0] = matrix[i][0] - '0';
            maxSide = std::max(maxSide, dp[i][0]);
        }
        
        for(int i=1; i<r; ++i) {
            for(int j=1; j<c; ++j) {
                if(matrix[i][j] == '1') {
                    dp[i][j] = std::min(dp[i-1][j-1], std::min(dp[i-1][j], dp[i][j-1])) + 1;
                    if(dp[i][j] > maxSide) maxSide = dp[i][j];
                }
            }//--for
        }//--for
        
        return maxSide * maxSide;

LC363: Max sum of rectangle no larger than K