Chapter 31 Sliding Window

31.1 76. 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).
For example, S = “ADOBECODEBANC”, T = “ABC”
Minimum window is “BANC”.
Note: If there is no such window in S that covers all characters in T, return the empty string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

https://leetcode.com/problems/minimum-window-substring/

注意:

1. T的字符可以重复.比如s=“a”, t=“aa”,结果应该是"".
2. 还有window里面不用考虑字符的顺序,只要包含字符就行.

难点是如何判定一个window是valid的,和如果移动窗口到下一个有效的窗口.

最优解来自Hashmap(Counter) + Two pointer. 写法可以有不同.

• Algo 1 - counter is the unique char number in t

struct Solution { // 123 ms 21%
  string minWindow(string s, string t) {
    unordered_map<char, int> mp; // work load
    for (char now : t) mp[now] ++; // counter
    int hd = 0, tl = 0, len = INT_MAX, c = mp.size(); // unique char #
    string r;
    while (hd < s.size()) { // loop through s
      if (mp.count(s[hd]) == 0) { ++hd; continue; }// skip无关项
      while (c && tl < s.size()) { //扩展尾部减count
        if (mp.count(s[tl]) == 0) { tl++; continue; } //skip无关项
        if (--mp[s[tl]] == 0) c--;
        tl++;
      }//count==0表示发现了一个window了,也可能是tl走到头了
      if (c == 0 && tl - hd< len) len = tl - hd, r = s.substr(hd, len);
      if (mp[s[hd]]++ == 0) c++; // move head forward
      ++hd;
    }
    return r;
  }
};

c是t里面unique char的个数. 注意14行不能移动到里面那个while loop里去,因为c==0的时候,hd还可以继续前进.比如“acbbaca”,窗口是“bbaca”的时候c是0,不会进入里面那个while loop,但是hd还会继续前进,直到得到结果“baca”.

loop里面有很多continue的时候最好用for loop,不然while loop很容易写出死循环.

这个算法和rolling hash有异曲同工之妙.非常厉害.

我认为速度慢的原因是用了map. a letter array should be enough. 还有每次都很浪费的substr(). record start and end should be enough.

在语言的层面进行了一些优化,立刻快了10倍:

struct Solution { // 9ms, 73.77%
  string minWindow(string s, string t) {
    char mp[256]={};
    bool n[256]={};
    int count=0;
    for (char c : t){ if(mp[c]==0){ count++, n[c]=true; }; mp[c]++; }// counter
    int j = 0, ans = INT_MAX, head=0, tail=0;
    for (int i = 0; i < s.size(); i++) { // loop through s
        if (n[s[i]] == 0) { continue; }
        while (count && j<s.size()) {
            if (n[s[i]] == 0) { j++; continue; }
            mp[s[j]]--;
            if (mp[s[j]] == 0) count--;
            j++;
        }
        if (count == 0 && j - i< ans)
            ans = j - i, head=i, tail=j;
        if (mp[s[i]] == 0) count++;
        mp[s[i]]++;
    }
    return s.substr(head, tail-head);
  }
};

上面的算法思路清晰,但是if (mp.count(s[i]) == 0) { continue; }其实可以不需要.

• Algo 2 - counter is all the char number in t

下面这个是最优解\(O(N)\). 前向型双指针,先移动尾巴再移动头.

struct Solution {// 9ms
    string minWindow(string s, string t) {
        int m[128] = {}; //unordered_map<char, int> m;
        for(char c: t) m[c]++;
        int h=0, hd=0, tl=0, len=2147483647, count=t.size();
        while(tl < s.size()){//  move tail forward
            if(m[s[tl]]>0) --count;//count,1
            m[s[tl]]--;
            while(count==0){// found a window and move head forwad
                if(tl-hd+1 < len)
                    len = tl-hd+1, h=hd;// backup head, update `len` before moving
                m[s[hd]]++;
                if(m[s[hd]]>0) ++count; // in this case, s[hd] must be a char in t
                hd++;
            }
            tl++;
        }
        return len==2147483647?"":s.substr(h,len);
    }
};

与算法1不同的是, count是t的size(). 为什么非t里面的字母不会screw things up,因为两次扫描,一次加一次减,最多等于0,不会大于0. count的加减都是在m[s[i]]大于0的时候进行.

https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems/11

---

Here comes the template.

For most substring problem, we are given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. The template is given below.

[cling]$ (int)'z'
(int) 122
[cling]$ (int)'Z'
(int) 90
[cling]$ (int)'9'
(int) 57

int findSubstring(string s){
   vector<int> map(128,0);
   int counter; // check whether the substring is valid
   int begin=0, end=0; //two pointers, one point to tail and one  head
   int d; //the length of substring
   for() { /* initialize the hash map here */ }
   while(end<s.size()){
       if(map[s[end++]]-- ?){  /* modify counter here */ }
       while(/* counter condition */){
            /* update d here if finding minimum*/
           //increase begin to make it invalid/valid again
           if(map[s[begin++]]++ ?){ /*modify counter here*/ }
       }  
       /* update d here if finding maximum*/
   }
   return d;
}

One thing needs to be mentioned is that when asked to find maximum substring, we should update maximum after the inner while loop to guarantee that the substring is valid. On the other hand, when asked to find minimum substring, we should update minimum inside the inner while loop.

• The code of solving Longest Substring with At Most Two Distinct Characters is below:

int lengthOfLongestSubstringTwoDistinct(string s) {
    vector<int> map(128, 0);
    int counter=0, begin=0, end=0, d=0;
    while(end<s.size()){
        if(map[s[end++]]++==0) counter++;
        while(counter>2) if(map[s[begin++]]--==1) counter--;
        d=max(d, end-begin);
    }
    return d;
}

• The code of solving Longest Substring Without Repeating Characters is below:

Update 01.04.2016, thanks weiyi3 for advise.

int lengthOfLongestSubstring(string s) {
    vector<int> map(128,0);
    int counter=0, begin=0, end=0, d=0;
    while(end<s.size()){
        if(map[s[end++]]++>0) counter++;
        while(counter>0) if(map[s[begin++]]-->1) counter--;
        d=max(d, end-begin); //while valid, update d
    }
    return d;
}

---

Let me explain this algorithm.

1. Use two pointers: start and end to represent a window.
2. Move end to find a valid window.
3. When a valid window is found, move start to find a smaller window.

To check if a window is valid, we use a map to store (char, count) for chars in t. And use counter for the number of chars of t to be found in s. The key part is m[s[end]]--;. We decrease count for each char in s. If it does not exist in t, the count will be negative.

To really understand this algorithm, please see my code which is much clearer, because there is no code like if(map[s[end++]]++>0) counter++;.

string minWindow(string s, string t) {
  unordered_map<char, int> m;
  // Statistic for count of char in t
  for (auto c : t) m[c]++;
  // counter represents the number of chars of t to be found in s.
  size_t start = 0, end = 0, counter = t.size(), minStart = 0, minLen = INT_MAX;
  size_t size = s.size();

  // Move end to find a valid window.
  while (end < size) {
    // If char in s exists in t, decrease counter
    if (m[s[end]] > 0)
      counter--;
    // Decrease m[s[end]]. If char does not exist in t, m[s[end]] will be negative.
    m[s[end]]--;
    end++;
    // When we found a valid window, move start to find smaller window.
    while (counter == 0) {
      if (end - start < minLen) {
        minStart = start;
        minLen = end - start;
      }
      m[s[start]]++;
      // When char exists in t, increase counter.
      if (m[s[start]] > 0)
        counter++;
      start++;
    }
  }
  if (minLen != INT_MAX)
    return s.substr(minStart, minLen);
  return "";
}

The code above costs 76ms. If we change the first line unordered_map<char, int> m; to vector<int> m(128, 0);, it costs 12ms.

1. (Linkedin) coding5: minimum substring that contains the given characters,秒了,刚想写代码.大哥说,你做过吗?我说没啊.他说,我觉得你idea对的,咱换个题..我..后来换成不给string, 给一个string iterator,用HasNext和next接口. 后来也写出来了.

2. (facebook) LC的minimum window substring,唯一一点不同的是说我们要找的substring是无重复的. 写的函数应该是这样: public String minWindow(String S, String sub) sub字符串中无重复字符. 前两天才写过这题,当时哗啦啦5分钟,然后当时电面脑抽,又紧张,估计也写了十几二十分钟,写完了后来被小哥说:你的更新长度的条件检查有问题.然后我又跑回去改,弱智错误…后来又问这个方法的O是多少,我说,是\(O(n)\),把为什么是\(O(n)\)跟他说了

31.2 159. Longest Substring with At Most Two Distinct Characters

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

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

For example, Given s = “eceba”, T is “ece” which its length is 3.

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {//Two pointers + hashtable
        int i=0, j=0, L=s.size(), r=0, c=0;
        uint32_t m[256]={0};
        while (j<L){
            if (++m[s[j]]==1) c++;
            if (c>2){
                if (--m[s[i]]==0) c--;
                ++i;
            }
            r=max(r, ++j-i);
        }
        return r;
    }
};

31.3 3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int m[128]={};
        int head=0, cur=0, h=0, L=s.size(), len=0, dup=0;
        while(cur<L){
            if(m[s[cur++]]++ > 0) dup++;
            while(dup>0) if(m[s[head++]]-- > 1) dup--;
            len=max(len,cur-head);
        }
        return len;
    }
};

https://leetcode.com/articles/longest-substring-without-repeating-characters/

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}

31.4 438. Find All Anagrams in a String

https://leetcode.com/problems/find-all-anagrams-in-a-string

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

anagram说明是substring,不是subsequence.要稍微容易点.

• Algo 1 - Sliding window

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (s.empty()) return {};
        vector<int> r;
        int m[128]={};
        for (char c : p) ++m[c];
        int hd = 0, tl = 0, L = s.size(), N=p.size(), cnt=N;
        while (tl < L) {
            if (m[s[tl]] > 0) --cnt;
            m[s[tl]]--;
            if (cnt == 0) r.push_back(hd);
            if (tl-hd+1 == N){ // move head
                ++m[s[hd]];
                if(m[s[hd]] > 0){ ++cnt; }
                ++hd;
            }
            tl++;
        }
        return r;
    }
};

这里不用while用if是因为求的是substring.

• Algo 2 - Compare vector/set

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (s.empty()) return {};
        vector<int> res, m1(128, 0), m2(128, 0);
        int N=p.size();
        for (int i = 0; i < N; ++i)
            ++m1[s[i]], ++m2[p[i]];
        if (m1 == m2)
            res.push_back(0);
        for (int i = N; i < s.size(); ++i) {
            ++m1[s[i]], --m1[s[i - N]]; //Add one, Subtract one
            if (m1 == m2)
                res.push_back(i - N + 1);
        }
        return res;
    }
};

因为是substring,所以可以用这个办法. subsequence就不行了.

31.5 239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].
Note: You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.
Follow up: Could you solve it in linear time?

https://leetcode.com/problems/sliding-window-maximum/

使用monotinic deque.

struct Solution {
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> q;
    vector<int> maxs;
    if(nums.empty()|| k<=0) return maxs;
    for (int i=0; i<nums.size(); i++) {
      while(!q.empty() && nums[q.back()]<=nums[i]) 
        q.pop_back();
      q.push_back(i);
      if(q.front()<=i-k) q.pop_front();
      if(i>=k-1) maxs.push_back(nums[q.front()]);
    }
    return maxs;
  }
};

31.6 480. Sliding Window Median

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,

Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Median
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6
Therefore, return the median sliding window as [1,-1,-1,3,5,6].

https://leetcode.com/problems/sliding-window-median/

struct Solution {
  vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    multiset<int> window(nums.begin(), nums.begin() + k);
    auto mid = next(window.begin(), k / 2);
    vector<double> medians;
    for (int i=k; ; i++) {
      medians.push_back((double(*mid) + *prev(mid, 1 - k%2)) / 2);
      if (i == nums.size())
          return medians;
      window.insert(nums[i]);
      if (nums[i] < *mid) mid--;
      if (nums[i-k] <= *mid) mid++;
      window.erase(window.lower_bound(nums[i-k]));
    }
  }
};

http://bit.ly/2womeRR

31.7 632. Smallest Range

You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:
The given list may contain duplicates, so ascending order means >= here.
1 <= k <= 3500
-105 <= value of elements <= 105.
For Java users, please note that the input type has been changed to List<List>. And after you reset the code template, you’ll see this point.

https://leetcode.com/problems/smallest-range/

这题完全可以套用上面的模板,把所有的点(pair of value and row index)放到一个vector里面,然后sort,然后双指针.

不过根据这题的特点, 下面用一个priority_queue + 一个list当做deque使用 + 一个vector当map + 一个counter搞定.

using PII=pair<int,int>; // <value, vec row index>
struct cmp{ bool operator()(PII& p1, PII& p2){return p1.first>p2.first;} };
struct Solution {
  vector<int> smallestRange(vector<vector<int>>& nums) {
    priority_queue<PII, vector<PII>, cmp> q;
    int ROW=nums.size(), count=0, r=INT_MAX;
    for(int i=0;i<ROW;++i)
      for(int j=0;j<nums[i].size();++j)
        q.push({nums[i][j], i});
    vector<int> m(ROW), rr; // counter
    list<PII> dq;
    while (!q.empty()){
      auto t = q.top();
      dq.push_back(t), q.pop();
      if(m[t.second]++ == 0) count++;
      while(count == ROW){
        const PII &y=dq.back(), &x=dq.front();
        int k=y.first-x.first;
        if(k<r) r=k, rr={x.first, y.first};
        m[x.second]--, dq.pop_front();
        if(m[x.second]==0) count--;
      }
    }
    return rr;
  }
};

这题采用Merge K Sorted List的方法解更简单. 刚开始也想过这个方法,以为要用young tableau的数据结构才能解,后来发现不必要,直接PQ+max value就可以了.代码: https://goo.gl/zK26q2

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        typedef vector<int>::iterator vi;
        struct comp {
            bool operator()(pair<vi, vi>& p1, pair<vi, vi>& p2) {
                return *p1.first > *p2.first;
            }
        };
        int hi = INT_MIN;
        priority_queue<pair<vi, vi>, vector<pair<vi, vi>>, comp> pq;
        for (auto &row : nums) {
            hi = max(hi, row[0]);
            pq.push({row.begin(), row.end()});
        }
        vector<int> ans = {*pq.top().first, hi};
        while (true) {
            auto p = pq.top();
            pq.pop();
            ++p.first;
            if (p.first == p.second) break;
            pq.push(p);
            int lo = *pq.top().first;
            hi = max(hi, *p.first);
            if (hi - lo < ans[1] - ans[0])
                ans = {lo, hi};
        }
        return ans;
    }
};