# Fruits Into Baskets

## Problem

Given an array of characters where each character represents a fruit tree, you are given **two baskets**, and your goal is to put **maximum number of fruits in each basket**. The only restriction is that **each basket can have only one type of fruit**.

You can start with any tree, but you can’t skip a tree once you have started. You will pick one fruit from each tree until you cannot, i.e., you will stop when you have to pick from a third fruit type.

Write a function to return the maximum number of fruits in both the baskets.

{% hint style="info" %}
For example:

```
Input: Fruit=['A', 'B', 'C', 'A', 'C']
Output: 3
Explanation: We can put 2 'C' in one basket 
and one 'A' in the other from the subarray 
['C', 'A', 'C']
```

```
Input: Fruit=['A', 'B', 'C', 'B', 'B', 'C']
Output: 5
Explanation: We can put 3 'B' in one basket 
and two 'C' in the other basket. This can be 
done if we start with the second letter: 
['B', 'C', 'B', 'B', 'C']
```

{% endhint %}

### Thought Process

* This question is very similar to Longest Substring with K Distinct Characters but in this problem it's the longest subarray with 2 distinct characters (i.e fruits)

* In this problem we need to find the length of the longest subarray with no more than two distinct characters (or fruit types!)

* Use a dictionary so we can keep track of how many fruits we have

## Solution

```
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        fruitBasket = {}
        maxLength = 0
        start = 0
        
        for i in range(len(tree)):
            if tree[i] not in fruitBasket:
                fruitBasket[tree[i]] = 1
            fruitBasket[tree[i]] +=1
            
            while len(fruitBasket) > 2:
                leftFruit = tree[start]
                fruitBasket[leftFruit]-=1
                if fruitBasket[leftFruit] == 1:
                    del fruitBasket[leftFruit]
                start+=1
            
            maxLength = max(maxLength, i - start + 1)
            
        return maxLength
        
```

## Key Points

* This problem can be represented as we need to find the longest subarray with no more than 2 distnct elements.

* We are using a static window but according to the condition that there must be only 2 distinct characters in this window, which we will know is true or not according to our dictionary length.

* We are using a dictionary to keep track of the number of distinct fruits.

## Time Complexity

* **Time:** $$O(n)$$ 

* **Space:** $$O(1)$$as there can be a maximum of three types of fruit stored in the frequency map. It's not O(K) because we already know K, which is 2.