# LC 904. Fruit Into Baskets

### [Problem link](https://leetcode.com/problems/fruit-into-baskets/)

###### tags: `leedcode` `medium` `python` `c++` `Sliding Window`

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array <code>fruits</code> where <code>fruits[i]</code> is the **type** of fruit the <code>i^th</code> tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

- You only have **two** baskets, and each basket can only hold a **single type** of fruit. There is no limit on the amount of fruit each basket can hold.
- Starting from any tree of your choice, you must pick **exactly one fruit** from **every** tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
- Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array <code>fruits</code>, return the **maximum** number of fruits you can pick.

**Example 1:**

Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.

**Example 2:**

Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].

**Example 3:**

Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].

**Constraints:**

- <code>1 <= fruits.length <= 10⁵</code>
- <code>0 <= fruits[i] < fruits.length</code>

## Solution 1 - Sliding Window
#### Python

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        d = defaultdict(int)
        res = 0
        start = 0

        for idx, val in enumerate(fruits):
            d[val] += 1
            while len(d) > 2:
                d[fruits[start]] -= 1
                if d[fruits[start]] == 0:
                    del d[fruits[start]]
                start += 1

            res = max(res, idx - start + 1)

        return res

#### C++

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> cnt;
        int ans = 0;
        int l = 0;
        for (int r = 0; r < fruits.size(); r++) {
            cnt[fruits[r]]++;
            if (cnt.size() > 2) {
                cnt[fruits[l]]--;
                if (cnt[fruits[l]] == 0) {
                    cnt.erase(fruits[l]);
                }
                l++;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
題目轉一下就變成最多兩個不同字母的最長子字串長度, 跟LC 159基本一樣.