# 904 - Fruit Into Baskets

解法一 - Sliding window

這題的 maximum number of fruit 指的是 maximum window size，然後因為只有兩個 basket，所以這個 window 裡面只能有兩種 char。所以其實就跟 # 340 - Longest Substring with At Most K Distinct Characters 一樣，只是 k 固定是 2。

正確的解法如下：

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int maxLength = 0;

        unordered_map<int, int> table;
        int windowStart = 0;

        for(int windowEnd = 0; windowEnd<tree.size(); windowEnd++) {
            table[tree[windowEnd]]++;

            while(table.size() > 2) {
                if(--table[tree[windowStart]] == 0)
                    table.erase(tree[windowStart]);
                windowStart++;
            }


            // Compare maxLength after assuring there are less
            // than 2 diff. fruit type
            maxLength = max(maxLength, windowEnd-windowStart+1);
        }

        return maxLength;
    }
};

我很直覺都會想要用下面的實作方法，也就是在 while 前就先判斷：

if(table.size() <= 2) {
    maxLength = max(maxLength, windowEnd-windowStart+1);
}

可是這樣會漏考慮一些 case，比如說剛出 while，這時的 fruit type 也在兩種以下，應該要再算算看這時的 window size 有沒有比 maxLength 大，但我會直接進到下一輪，把 windowEnd 增加然後放入新的 fruit，所以就漏考慮了剛剛的 case。下面是錯誤版本的實作：

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int maxLength = 0;

        unordered_map<char, int> table;
        int windowStart = 0;

        for(int windowEnd = 0; windowEnd<tree.size(); windowEnd++) {
          table[tree[windowEnd]]++;

          if(table.size() <= 2) {
            maxLength = max(maxLength, windowEnd-windowStart+1);
          }

          while(table.size() > 2) {
            if(--table[tree[windowStart]] == 0)
              table.erase(tree[windowStart]);
            windowStart++;
          }
        }

        return maxLength;
    }
};