In a row of trees, the i-th tree produces fruit with type tree[i].
You start at any tree of your choice, then repeatedly perform the following steps:

Add one piece of fruit from this tree to your baskets.  If you cannot, stop.
Move to the next tree to the right of the current tree.  If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.
You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.
What is the total amount of fruit you can collect with this procedure?
 
Example 1:
Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].


Example 2:
Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].


Example 3:
Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].


Example 4:
Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.

 



Note:

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

Difficulty: interview

Starter code:

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        

Solutions:
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        prior_fruit = tree[0]
        prior_fruit_counter = 0
        fruits_in_basket = [tree[0]]
        fruits_in_basket_counter = 0
        max_fib = -1
        for fruit in tree: 
            if prior_fruit == fruit:
                prior_fruit_counter += 1
                fruits_in_basket_counter += 1
            elif prior_fruit != fruit:
                if fruit in fruits_in_basket:
                    fruits_in_basket_counter += 1
                else:
                    fruits_in_basket, fruits_in_basket_counter = [prior_fruit, fruit], prior_fruit_counter + 1
                prior_fruit, prior_fruit_counter = fruit, 1
            if fruits_in_basket_counter > max_fib:
                max_fib = fruits_in_basket_counter
        return max_fib

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        best_so_far = start = 0
        fruit_1 = fruit_2 = fruit_1_last_index = fruit_2_last_index = None
        
        for end in range(len(tree)):
            if fruit_1 is None:
                fruit_1 = tree[end]
                fruit_1_last_index = end
                
            elif fruit_2 is None and tree[end] != fruit_1:
                fruit_2 = tree[end]
                fruit_2_last_index = end
                
            else:
                if tree[end] == fruit_1:
                    fruit_1_last_index = end
                elif tree[end] == fruit_2:
                    fruit_2_last_index = end
                else:
                    best_so_far = max(best_so_far, end - start)
                    
                    if fruit_1_last_index < fruit_2_last_index:
                        start = fruit_1_last_index + 1
                        fruit_1 = tree[end]
                        fruit_1_last_index = end
                    else:
                        start = fruit_2_last_index + 1
                        fruit_2 = tree[end]
                        fruit_2_last_index = end
        
        return max(best_so_far, len(tree) - start)

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        q = []
        ans = -99999999999
        s = 0
        e = s
        while e<len(tree):
            if tree[e] not in q:
                if len(q)<2:
                    q.append(tree[e])
                else:
                    if e-s > ans:
                        ans = e-s
                    i = e-1
                    while tree[i] == tree[e-1] and i>-1:
                        i -= 1
                    s = i+1
                    q.clear()
                    q.append(tree[s])
                    q.append(tree[e])
                
            e += 1
        
        if e-s > ans:
            ans = e-s
        
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        tran_ptr = 0
        maxlist = []
        
        while True:
            scan_ptr = tran_ptr
            count = 0
            types = []
            
            # Scan pointer reaches the end of tree[]
            # or until finding 3rd type of fruit
            while True:
                if tree[scan_ptr] in types:
                    count += 1
                elif len(types) == 0:
                    types.append(tree[scan_ptr])
                    count += 1
                elif len(types) == 1:
                    tran_ptr = scan_ptr
                    types.append(tree[scan_ptr])
                    count += 1
                else: # New type of fruit and types are full
                    break
                scan_ptr += 1
                if scan_ptr == len(tree):
                    break
            maxlist.append(count)
            
            if scan_ptr == len(tree):
                break
        
        return max(maxlist)

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        window = collections.Counter()
        ans = 0
        
        left = 0
        for right in range(len(tree)):
            window[tree[right]] += 1
            while len(window) > 2:
                window[tree[left]] -= 1
                if window[tree[left]] == 0:
                    del window[tree[left]]
                left += 1
                
            ans = max(ans, sum(window.values()))
            
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        maxi=0
        if len(tree)==1:
            return 1
        l=[]
        s=set()
        for i in range(len(tree)):
            l.append(tree[i])
            s.add(tree[i])
            if len(s)>2:
                #l=l[::-1]
                while len(set(l))>2:
                    #l.pop()
                    l=l[1:]
                #l=l[::-1]
            maxi=max(maxi,len(l))
        return maxi
        
#         maxi=0
#         if len(tree)==1:
#             return 1
            
#         for i in range(len(tree)):
#             s=set()
#             s.add(tree[i])
#             for j in range(i+1,len(tree)):
#                 s.add(tree[j])
#                 if len(s)>2:
#                     break
#                 maxi=max(maxi,j-i+1)
#         return maxi
        
        # for i in range(len(tree),0,-1):
        #     start=0
        #     end=i
        #     for j in range(len(tree)-i+1):
        #         s=tree[start:end]
        #         start+=1
        #         end+=1
        #         if len(set(s))<=2:
        #             return i


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        res = 0
        max_elem_count = 0
        window = {}
        start = 0
        
        l = len(tree)
        for end in range(l):
            if tree[end] in window:
                window[tree[end]] += 1
            else:
                window[tree[end]] = 1
            max_elem_count = max(max_elem_count, window[tree[end]])
            
            while len(window) > 2:
                window[tree[start]] -= 1
                if window[tree[start]] == 0:
                    window.pop(tree[start])
                start += 1
                
            res = max(res, end - start + 1)
        
        return res

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        # find the largest region using only two numbers..
        # sliding window may do the trick here
        # use a dictionary to keep track of the fruits/ how many types you have .. or just use two baskekts
        import collections
        fruits = collections.defaultdict(int)
        # only put something in the basket if it's empty
        max_len = 0
        front = back = 0
        while back < len(tree):
            if len(list(fruits.keys())) <= 2:
                fruits[tree[back]] += 1
                back += 1
            else:
                fruits[tree[front]] -= 1
                if fruits[tree[front]] == 0:
                    del fruits[tree[front]]
                front += 1
            if len(list(fruits.keys())) <= 2:
                max_len = max(max_len, back-front)
        return max_len


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if not tree:
            return 0
        
        max_count = 1
        basket = {tree[0]: 1}
        i = 0
        for j in range(1, len(tree)):
            basket[tree[j]] = basket.get(tree[j], 0) + 1
            while (len(basket) > 2):
                # remove tree[i], decrement i
                basket[tree[i]] = basket.get(tree[i], 0) - 1
                if (basket[tree[i]] == 0):
                    basket.pop(tree[i])
                i += 1
            curr_count = sum(basket.values())
            max_count = max(max_count, curr_count)
        
        return max_count
        
            
        


class Solution:
    def totalFruit(self, tree: List[int]) -> int:

        p1 = 0
        p2 = 0
        counter = 0
        mx = 0
        mmap = {}
        uniq = set()
        while p2 < len(tree):
            if len(uniq) > 2:
                # remove here
                mmap[tree[p1]] -= 1
                if mmap[tree[p1]] == 0:
                    uniq.remove(tree[p1])
                    
                p1 += 1
                #print(mmap, uniq, p1, p2)
            else:
                # add here
                if tree[p2] in mmap:
                    mmap[tree[p2]] += 1
                else:
                    mmap[tree[p2]] = 1
                    
                uniq.add(tree[p2])
                if len(uniq) <= 2:
                    counter = p2 - p1 + 1
                mx = max(mx, counter)  
                p2 += 1
                
                
        return mx
                
            
    
            
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if len(set(tree))<=2:
            return len(tree)
        res = cur = count_b = a = b = 0

        for c in tree:
            cur = cur + 1 if c in (a, b) else count_b + 1
            count_b = count_b + 1 if c == b else 1
            if b != c: a, b = b, c
            res = max(res, cur)
        return res

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        fruit_types = collections.Counter()
        max_fruit = 0
        
        start_idx = 0
        end_idx = 0
        
        # Move end pointer forward
        while end_idx < len(tree):
            fruit_types[tree[end_idx]] += 1
            
            # Move start pointer forward
            while len(fruit_types) > 2:
                fruit_types[tree[start_idx]] -= 1
                if fruit_types[tree[start_idx]] == 0:
                    del fruit_types[tree[start_idx]]
                start_idx += 1
                
            max_fruit = max(max_fruit, sum(fruit_types.values()))
            
            end_idx += 1
        
        return max_fruit

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        #You want a basket that can get both. 
        total_fruits = collections.defaultdict(int)
        unique_baskets = 0
        max_fruit_types = 0 
        start = 0
        for end in range(len(tree)):
            cur_fruit = tree[end]
            total_fruits[cur_fruit] += 1 
            if total_fruits[cur_fruit] == 1: #then we know there is a unique fruit here
                unique_baskets += 1 
                
            while unique_baskets >= 3: 
                start_fruit = tree[start]
                total_fruits[start_fruit] -= 1
                if not total_fruits: #this means that we have less unique baskets now 
                    unique_baskets -= 1 
                start += 1
                    
            max_fruit_types = max(max_fruit_types, end - start + 1)
            
        return max_fruit_types
            
#         #Start at ANY tree of my choice 
#         #Then perform the steps 
# #         1) Add one fruit from the tree to basket. If you can't you stp 
# #         2) Move to the next tree to the RIGHT of the current tree if there is no such tree you stop. 
        
#     #So you reset back to step 1 after you're done. 
#     #So this means that once you're done and because we want to GET all possible fruits through your positions 
# #         WANT: Total amount of fruit collected 
#         last_fruit = -1 
#         second_last_fruit = -1 
#         last_fruit_count = 0
#         total_fruits = 0 
#         cur_fruits_max = 0 
#         #Let's call prev fruits 
#         #last_fruit, second_last_fruit 
#         # fruit is our CURRENT fruit 
        
#         #So we have 2 prev fruit and current fruit.  
#         #If fruit is the second_last_fruit 
#         #We will know 
#         for fruit in tree: 
#             if fruit == last_fruit or fruit == second_last_fruit: 
#                 cur_fruits_max += 1 
                
#             else: 
#                 cur_fruits_max = last_fruit_count + 1 #this means we picked you new fruit 
                
     
#             #You need to check fruit with last fruit not second to last fruit since last fruit will be your \"best case scenario\"
#             if fruit == last_fruit: 
#                 last_fruit_count += 1 
#             else: 
#                 last_fruit_count = 1 #never been seen before (base case)
            
#             #This means that we'd be double counting if we moved you beforehand 
#             if fruit != last_fruit: #meaning your a second_last_fruit basically 
#                 second_last_fruit = last_fruit 
#                 last_fruit = fruit 
                
#             total_fruits = max(total_fruits, cur_fruits_max)
            
#         print(total_fruits)
#         # (O(N)) run time 
#         return total_fruits 
class Solution():
    def totalFruit(self, tree):
        fruit_basket = collections.defaultdict(int)
        unique_fruits = 0 
        total_fruits = 0 
        start = 0
        end = 0 
        for end in range(len(tree)): 
            type_of_fruit = tree[end]
            fruit_basket[type_of_fruit] += 1 #Defaultdict so if not there instantiate it and add one 
            #small check to count it one time for the fruit 
            if fruit_basket[type_of_fruit] == 1: 
                unique_fruits += 1 
                
            while unique_fruits > 2:
                start_fruit = tree[start]
                fruit_basket[start_fruit] -= 1 
                if not fruit_basket[start_fruit]: #meaning it's empty 
                    unique_fruits -= 1 
                start += 1 
            total_fruits = max(total_fruits, end - start + 1)
        return total_fruits
        
#Map Way   
# import collections
# class Solution():
#     def totalFruit(self, tree):
#         count = collections.defaultdict(int)
#         unique = res = end = start = 0
#         while end < len(tree):
#             count[tree[end]] += 1
#             if count[tree[end]] == 1: unique+=1
#             while unique > 2:
#                 count[tree[start]] -= 1
#                 if not count[tree[start]]: 
#                     unique -= 1
#                 start += 1
#             res = max(res, end - start + 1)
#             end += 1
#         return res
            
                
        
        
        
            
            
            




class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        ans, j = 0,0
        n = len(tree)
        dic = {}
        for i in range(n):
            dic[tree[i]] = i
            #print(dic, ans)
            if len(dic) > 2:
                ans = max(ans, i-j)
                k = None
                for key in dic:
                    if key != tree[i] and key !=tree[i-1]:
                        k = key
                        j = dic[key]+1
                del dic[k]
                
        return max(ans, n-j)
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        nTrees, ans = len(tree), 0
        if len(set(tree)) <= 2:
            return nTrees
        i, j = 0,1
        while i < j and j < nTrees:
            if len(set(tree[i:j+1])) <= 2:
                j += 1
                ans = max(ans, j-i)
            else:
                i+= 1
        return ans


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        i = 0
        count = collections.Counter()
        for index, value in enumerate(tree):
            count[value] += 1
            if len(count) > 2:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i +=1
        return len(tree) - i


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        '''
        Using sliding window, keep track of the longest window length where unique fruit types <= 2
        the max window will be the answer
        '''
        left = 0
        n = len(tree)
        ans = 0
        basket = set()
        counter = collections.Counter()
        for right, fruit in enumerate(tree):
            basket.add(fruit)
            counter[fruit] += 1
            while len(basket) > 2:
                counter[tree[left]] -= 1
                if counter[tree[left]] == 0:
                    basket.remove(tree[left])
                left += 1
            ans = max(ans, right-left+1)
        return ans
        
        # # Recursive
        # memo = {}
        # def collect(index, basket=[]):
        #     if index == len(tree):
        #         return 0
        #     # if (index, set(basket)) 
        #     take = 0
        #     if len(basket) < 2 or (tree[index] in basket):
        #         take = collect(index+1, basket+[tree[index]]) + 1
        #     skip = 0
        #     if len(basket) < 2:
        #         skip = collect(index+1, basket)
        #     return max(take, skip)
        # return collect(0)                        


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        ans = i = 0
        count = collections.Counter()
        for j, x in enumerate(tree):
            count[x] += 1
            while len(count) >= 3:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        # Goal is to find longest continuous subsequence containing only 2 types
        ans = i = 0
        count = Counter()
        for j, t in enumerate(tree):
            count[t] += 1
            while len(count) > 2:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i += 1

            ans = max(ans, j - i + 1)
        return ans


class Solution(object):
    def totalFruit(self, tree):
        ans = i = 0
        count = collections.Counter()
        for j, x in enumerate(tree):
            count[x] += 1
            while len(count) >= 3:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans

class Solution:
     def totalFruit(self, tree: List[int]) -> int:
            start = 0
            max = 0
            reset = 0
            baskets ={1: [None, 0], 2: [None, 0]}
            while start < len(tree) and start >= 0:
                if baskets[1][0] == None:
                    baskets[1][0] = tree[start]
                    baskets[1][1] += 1
                    while reset and start > 0:
                        if baskets[1][0] != tree[start -1]:
                            reset = 0
                        else:
                            start -= 1
                elif baskets[1][0] == tree[start]:
                    baskets[1][1] += 1
                elif baskets[2][0] == None:
                    baskets[2][0] = tree[start]
                    baskets[2][1] += 1
                elif baskets[2][0] == tree[start]:
                    baskets[2][1] += 1
                else:
                    if max < baskets[1][1]+ baskets[2][1]:
                        print((baskets,start))
                    baskets ={1: [None, 0], 2: [None, 0]}
                    reset  = 1
                if reset == 1:
                    if start > 0:
                        start -= 1
                else:
                    start += 1
                if max < baskets[1][1]+ baskets[2][1]:
                    max  =  baskets[1][1]+ baskets[2][1]
            return max
        


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        finalMax = currentMax = last = secondLast = lastCount = 0

        for fruit in tree:
            if fruit == last or fruit == secondLast:
                currentMax += 1
            else:
                currentMax = lastCount + 1

            if fruit == last:
                lastCount += 1
            else:
                secondLast = last
                last = fruit
                lastCount = 1

            finalMax = max(finalMax, currentMax)

        return finalMax



from collections import Counter

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        max_fruits = 0
        window_start = 0
        freq = Counter()
        for i, val in enumerate(tree):
            freq[val] += 1
            while len(freq) > 2:
                to_delete = tree[window_start]
                freq[to_delete] -= 1
                if not freq[to_delete]:
                    del freq[to_delete]
                window_start += 1
            max_fruits = max(max_fruits, i - window_start + 1)
        return max_fruits

class Solution:
    def totalFruit(self, trees: List[int]) -> int:
        
        if len(trees) <= 2:
            return len(trees)
        
        lp = 0
        rp = 1
        maxSize = 0
        hash = collections.defaultdict(int)
        lpInc = False
        rpInc = False
        curSet = set()
        
        # Start the left and right pointer values at 1 frequency. Use += 1 in case trees[lp] and trees[rp] point to the same value.
        hash[trees[lp]] += 1
        curSet.add(trees[lp])
        hash[trees[rp]] += 1
        curSet.add(trees[rp])
        
        while rp < len(trees):
            if lpInc:
                hash[trees[lp-1]] = max(hash[trees[lp-1]]-1, 0)
                if hash[trees[lp-1]] > 0:
                    curSet.add(trees[lp-1])
                else:
                    curSet.remove(trees[lp-1])
            if rpInc:
                hash[trees[rp]] += 1
                curSet.add(trees[rp])
                
            lpInc = False
            rpInc = False
            
            if len(curSet) <= 2:
                if (rp - lp) + 1 > maxSize:
                    maxSize = (rp - lp) + 1
                    
            if len(curSet) > 2:
                lp += 1
                lpInc = True
            else:
                rp += 1
                rpInc = True
        
        return maxSize


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        i = 0
        j = 0
        hm = {}
        maxL = 0
        while j < len(tree):
            if tree[j] in hm:
                hm[tree[j]] += 1
            else:
                if len(hm)<2:
                    hm[tree[j]] = 1
                else:
                    maxL = max(maxL, j-i)
                    while i<j and len(hm)>1:
                        hm[tree[i]] -= 1
                        if hm[tree[i]] == 0:
                            del hm[tree[i]]
                        i += 1
                    hm[tree[j]] = 1

            j += 1

        maxL = max(maxL,j-i)
        return maxL


from collections import Counter

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        baskets = Counter()
        max_fr = 0
        i = 0
        
        for j, t in enumerate(tree):
            baskets[t] += 1
            
            while len(baskets) > 2:
                baskets[tree[i]] -= 1
                if baskets[tree[i]] == 0:
                    del baskets[tree[i]]
                
                i += 1
            
            max_fr = max(max_fr, j - i + 1)
        
        return max_fr

# class Solution:

#     def totalFruit(self, tree):
#         count, i = {}, 0
#         for j, v in enumerate(tree):
#             count[v] = count.get(v, 0) + 1
#             if len(count) > 2:
#                 count[tree[i]] -= 1
#                 if count[tree[i]] == 0: del count[tree[i]]
#                 i += 1
#         return j - i + 1


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        fruitCap = [0] * len(tree)
        fruitCap[-1] = 1
        
        fruitA = tree[-1]
        fruitB = None
        for i in reversed(list(range(len(tree) - 1))):
            if tree[i] == fruitA or tree[i] == fruitB:
                fruitCap[i] = fruitCap[i + 1] + 1
            elif fruitB == None:
                fruitCap[i] = fruitCap[i + 1] + 1
                fruitB = tree[i]
            else:
                fruitA = tree[i]
                fruitB = tree[i + 1]
                fruitCap[i] = getConsecutive(tree, i + 1) + 1
        
        print(fruitCap)
        return max(fruitCap)
    
def getConsecutive(tree, index):
    
    consecutive = 0
    fruit = tree[index]
    for i in range(index, len(tree)):
        if tree[i] == fruit:
            consecutive += 1
        else:
            break
    
    return consecutive


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        #tree = [0,1,6,6,4,4,6]
        max_fruits = 0
        counter = 0
        fruit_basket = set()
        i = 0
        while i < len(tree):
            if len(fruit_basket) < 2 :
                counter += 1
                fruit_basket.add(tree[i])
                if len(fruit_basket) == 2:
                    new_fruit_idx = i
            elif tree[i] in fruit_basket:
                counter += 1
            else:
                fruit_basket = set()
                max_fruits = max(counter,max_fruits)
                counter = 0
                i = new_fruit_idx - 1
            i += 1
        max_fruits = max(counter,max_fruits)
        return max_fruits

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        max_ = 0
        baskets = {}
        
        def get_other_tree(this_tree):
            trees = list(baskets.keys())
            return trees[1 - trees.index(this_tree)] if len(trees) == 2 else trees[0]
        
        for idx, tr in enumerate(tree):
            need_to_empty_1_basket = tr not in baskets and len(baskets) == 2
            if need_to_empty_1_basket:
                max_ = max(max_, sum(sum(baskets[b]) for b in baskets))
                last_tree = tree[idx - 1]
                other_tree = get_other_tree(last_tree)
                baskets = {last_tree: [baskets[last_tree][1], 0], tr: [0, 1]}
            else:
                there_is_another_tree = (tr not in baskets and len(baskets) == 1) or (tr in baskets and len(baskets) == 2)
                if there_is_another_tree:
                    other_tree = get_other_tree(tr)
                    baskets[other_tree] = [sum(baskets[other_tree]), 0]

                if tr not in baskets:
                    baskets[tr] = [0, 0]
                baskets[tr][1] += 1
                
        return max(max_, sum(sum(baskets[b]) for b in baskets))


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if not tree or len(tree) == 0:
            return 0
        max_ = 1
        mem = {}
        i,j = 0,0
        while j<len(tree):
            if len(mem) <=2:
                mem[tree[j]] = j
                j += 1
            if len(mem) > 2:
                min_ = len(tree) - 1
                for value in mem.values():
                    min_ = min(min_,value)
                i = min_ + 1
                del mem[tree[min_]]
            max_ = max(max_,j-i)
            
        return max_

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        max_ = 0
        baskets = {}
        
        def get_other_tree(this_tree):
            trees = list(baskets.keys())
            return trees[1 - trees.index(this_tree)] if len(trees) == 2 else trees[0]
        
        for idx, tr in enumerate(tree):
            if tr not in baskets and len(baskets) == 2:
                max_ = max(max_, sum(sum(baskets[b]) for b in baskets))
                last_tree = tree[idx - 1]
                other_tree = get_other_tree(last_tree)
                baskets = {last_tree: [baskets[last_tree][1], 0], tr: [0, 1]}
            else:
                there_is_another_tree = (tr not in baskets and len(baskets) == 1) or (tr in baskets and len(baskets) == 2)
                if there_is_another_tree:
                    other_tree = get_other_tree(tr)
                    baskets[other_tree] = [sum(baskets[other_tree]), 0]

                if tr not in baskets:
                    baskets[tr] = [0, 0]
                baskets[tr][1] += 1
                
        return max(max_, sum(sum(baskets[b]) for b in baskets))


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        pre=-1
        ans=a=b=0
        x=y=-1
        for cur in tree:
            if cur!=x and cur!=y:
                x,y=pre,cur
                a,b=b,1
            elif cur==pre:
                b+=1
            else:
                a+=b
                b=1
            if a+b>ans:
                ans=a+b
            pre=cur
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        # need to identify longest streak of two unique types of fruit
        
        # brute force 
        # 
        # loop i 
        #   
        #   loop j
        #       if dict < 2 then add unique character to dict
        #       if num encountered is not in dict and dict.len == 2 then break
        #  check if the counter > max if it is then set max to counter
        
#         answer = 0
#         counter = 0
#         dictionary = {}
#         # print(tree)
#         for i in range(len(tree)):
#             for j in range(i, len(tree)):
#                 # print('curr', tree[j], i, j)
#                 if tree[j] in dictionary:
#                     counter += 1
#                 elif tree[j] not in dictionary and len(dictionary) < 2:
#                     counter += 1
#                     dictionary[tree[j]] = tree[j]
#                 elif tree[j] not in dictionary and len(dictionary) == 2:
#                     break
#             # print('round done')
#             if counter > answer:
#                 answer = counter
#                 # print('reassigning answer', answer)
#             counter = 0
#             dictionary = {}
                
#         return answer

        # something faster
    
        answer = 0 
        currTree = 0
        numsDictionary = collections.Counter()
        
        for treeIndex, fruit in enumerate(tree):
            numsDictionary[fruit] += 1
            while len(numsDictionary) >= 3:
                numsDictionary[tree[currTree]] -= 1
                if numsDictionary[tree[currTree]] == 0:
                    del numsDictionary[tree[currTree]]
                currTree += 1
            answer = max(answer, treeIndex - currTree + 1 )
        return answer

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        i=0
        counter={}
        res=0
        for j, v in enumerate(tree):
            counter[v]=counter.get(v,0)+1
            while len(counter)>2:
                counter[tree[i]]-=1
                if not counter[tree[i]]: 
                    del counter[tree[i]]
                i+=1
            res=max(res, j-i+1)
        return res
                
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        i = 0
        next_start_pos = None
        max_len = 0
        s = set()
        res = []
        while i < len(tree):
            if tree[i] in s:
                max_len += 1
                i += 1
            else:
                if len(s) == 0:
                    s.add(tree[i])
                    max_len += 1
                    i += 1
                elif len(s) == 1:
                    s.add(tree[i])
                    max_len += 1
                    next_start_pos = i
                    i += 1
                elif len(s) == 2:
                    res.append(max_len)
                    max_len = 0
                    s = set()
                    i = next_start_pos
                    
        res.append(max_len)
        return max(res)

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        max_ = 0
        baskets = {}
        
        def get_other_tree(this_tree):
            trees = list(baskets.keys())
            return trees[1 - trees.index(this_tree)] if len(trees) == 2 else trees[0]
        
        for idx, tr in enumerate(tree):
            need_to_empty_1_basket = tr not in baskets and len(baskets) == 2
            if need_to_empty_1_basket:
                max_ = max(max_, sum(sum(counts) for counts in list(baskets.values())))
                last_tree = tree[idx - 1]
                other_tree = get_other_tree(last_tree)
                baskets = {last_tree: [baskets[last_tree][1], 0], tr: [0, 1]}
            else:
                there_is_another_tree = (tr not in baskets and len(baskets) == 1) or (tr in baskets and len(baskets) == 2)
                if there_is_another_tree:
                    other_tree = get_other_tree(tr)
                    baskets[other_tree] = [sum(baskets[other_tree]), 0]

                if tr not in baskets:
                    baskets[tr] = [0, 0]
                baskets[tr][1] += 1
                
        return max(max_, sum(sum(counts) for counts in list(baskets.values())))


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        left,right=-1,0
        seen = Counter()
        ans = 0
        while left<=right<len(tree):
            while right<len(tree) and (len(seen) < 2 or tree[right]in seen):
                seen[tree[right]]+=1
                right+=1
                
            ans = max(ans,right-left-1) #-1?

            left+=1
            seen[tree[left]]-=1
            if seen[tree[left]]==0:
                del seen[tree[left]]
                
        return ans

class Solution(object):
    def totalFruit(self, nums):
        d = {}
        k = 2
        maxL = 0
        L = 0
        
        for R in range(len(nums)):
            if nums[R] in d:
                d[nums[R]] += 1
            else:
                d[nums[R]] = 1
            while len(d) > k:
                d[nums[L]] -= 1
                if d[nums[L]] == 0:
                    del d[nums[L]]
                L+=1
            maxL = max(maxL, R-L+1)
        return maxL

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        maxi=0
        if len(tree)==1:
            return 1
        l=[]
        s=set()
        for i in range(len(tree)):
            l.append(tree[i])
            s.add(tree[i])
            if len(s)>2:
                l=l[::-1]
                while len(set(l))>2:
                    l.pop()
                l=l[::-1]
            maxi=max(maxi,len(l))
        return maxi
        
#         maxi=0
#         if len(tree)==1:
#             return 1
            
#         for i in range(len(tree)):
#             s=set()
#             s.add(tree[i])
#             for j in range(i+1,len(tree)):
#                 s.add(tree[j])
#                 if len(s)>2:
#                     break
#                 maxi=max(maxi,j-i+1)
#         return maxi
        
        # for i in range(len(tree),0,-1):
        #     start=0
        #     end=i
        #     for j in range(len(tree)-i+1):
        #         s=tree[start:end]
        #         start+=1
        #         end+=1
        #         if len(set(s))<=2:
        #             return i


class Track(object):
    def __init__(self, n = 2):
        # Maps the values to their counts
        self.count = {}
        
        # Keeps track of the last element
        self.last = {}
        self.order = [None for _ in range(n - 1)]
        
    def is_new_elem(self, elem):
        return elem not in self.count
    
    def is_last_elem(self, elem):
        return elem in self.last
    
    def add(self, elem):
        if self.is_new_elem(elem):
            self.count = {elem: 1}
            for key, val in self.last.items():
                self.count[key] = val
        else:
            self.count[elem] += 1
                
        if self.is_last_elem(elem):
            self.last[elem] += 1
        else:
            if elem in self.order:
                del self.order[self.order.index(elem)]
            else:
                rem = self.order.pop(0)
                if rem is not None:
                    del self.last[rem]
            
            self.last[elem] = 1
            self.order.append(elem)
        
    def get_count(self):
        total = 0
        for _, val in self.count.items():
            total += val
        return total
        
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        tracker = Track()
        
        max_count = 0
        for t in tree:
            tracker.add(t)
            max_count = max(max_count, tracker.get_count())
            
        
        return max_count

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        ans= i=0
        
        basket = {}
        
        for j, x in enumerate(tree):
            
            if x in basket:
                basket[x] += 1
            else:
                basket[x] = 1
                
            while len(basket)>=3:
                
                basket[tree[i]] -= 1
                
                if basket[tree[i]] == 0:
                    
                    del basket[tree[i]]
                
                i += 1
                
            ans = max(ans, j-i+1)
                
        return ans


class Solution:
    def totalFruit(self, tree) -> int:
        unit_first=tree[0]
        unit_second=-1
        amount_first=0
        amount_second=0
        max_amount=0
        prev=tree[0]
        prev_amount=0
        for i in range(len(tree)):
            if(tree[i] == prev):
                prev_amount+=1
            
            if(tree[i] == unit_first):
                amount_first+=1
            elif(tree[i] == unit_second):
                amount_second+=1
            else:
                max_amount = max(max_amount,(amount_first+amount_second))
                unit_first=prev
                amount_first=prev_amount
                unit_second=tree[i]
                amount_second=1
            
            if(tree[i] != prev):
                prev_amount=1

            prev = tree[i]

        return max(max_amount,(amount_first+amount_second))

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        b1, b2, b1N, b2N, b2NCons, maxPick = None, None, 0, 0, 0, 0

        for fruit in tree:

            if fruit == b2:
                b2N, b2NCons = b2N + 1, b2NCons + 1

            elif fruit == b1:
                b1, b2, b1N, b2N, b2NCons = b2, b1, b2N, b1N+1, 1

            else:
                b1, b2, b1N, b2N, b2NCons = b2, fruit, b2NCons, 1, 1

            maxPick = max(maxPick, b1N+b2N)

        return maxPick

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        ans = 0
        p = 0
        while p < len(tree):
            acc = 1
            first = tree[p]
            next_p = len(tree)
            second = -1
            for i in range(p + 1, len(tree)):
                if tree[i] != first:
                    if second == -1:
                        second = tree[i]
                        next_p = i
                    elif tree[i] != second:
                        break
                acc += 1
                if i == len(tree) - 1:
                    return max(ans, acc)
            p = next_p
            ans = max(ans, acc)
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        type_cnt = {}
        max_fruit = -1
        left_ptr = 0
        last_cnt = 0
        while left_ptr < len(tree):
            right_ptr = left_ptr
            while right_ptr < len(tree) - 1 and tree[right_ptr] == tree[right_ptr + 1]:
                right_ptr += 1
            curr_type = tree[left_ptr]
            curr_cnt = right_ptr - left_ptr + 1
                
            if curr_type not in type_cnt:
                type_cnt[curr_type] = curr_cnt
            else:
                type_cnt[curr_type] += curr_cnt

            if len(type_cnt) > 2:
                type_cnt = {last_type: last_cnt, curr_type: curr_cnt}
            
            max_fruit = max(max_fruit, sum([cnt for cnt in list(type_cnt.values())]))
            last_cnt = curr_cnt
            last_type = curr_type
            left_ptr = right_ptr + 1 
        return max_fruit
               


from collections import Counter

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        num_fruit = Counter()
        j, num_type, max_fruit = 0, 0, 0
        for i in range( len(tree) ):
            if num_fruit[ tree[i] ] == 0: num_type += 1
            num_fruit[ tree[i] ] += 1
            
            if num_type <= 2:
                max_fruit = max( i-j+1, max_fruit )
            else:
                while True:
                    num_fruit[ tree[j] ] -= 1
                    j += 1
                    if num_fruit[ tree[j-1] ] == 0: break
                num_type -= 1
        
        return max_fruit

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        result = 0
        collected = {}
        i = 0
        for j, fruit in enumerate(tree):
            collected[fruit] = collected.get(fruit, 0) + 1
            while len(collected) > 2:
                collected[tree[i]] -= 1
                if not collected[tree[i]]:
                    collected.pop(tree[i])
                i += 1
            result = max(result, j - i + 1)
        return result

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        ans = i = 0
        freq = collections.defaultdict(int)
        for j, fruit in enumerate(tree):
            freq[fruit] += 1
            while len(freq) == 3:
                freq[tree[i]] -= 1
                if freq[tree[i]] == 0:
                    del freq[tree[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if len(tree) < 2: return len(tree)
        start, end, res = 0, 1, 1
        basket = {tree[start]: 1}
        while end < len(tree):
            if tree[end] in basket:
                basket[tree[end]] +=1
                end += 1
                res = max(res, end-start)
            elif len(basket) < 2:
                basket[tree[end]] = 1
                end += 1
                res = max(res, end-start)
            else:
                basket[tree[start]] -= 1
                if basket[tree[start]] == 0:
                    del basket[tree[start]]
                start += 1
        return res

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        '''
        sliding window
        O(N)
        '''           
        if len(tree) == 1:
            return 1
        
        l = 0
        r = 1
        
        curr_window = defaultdict(int)
        curr_window[tree[l]] += 1 
        res = 1
        while r < len(tree):                                        
            curr_window[tree[r]] += 1
            while len(curr_window) > 2:                                    
                curr_window[tree[l]] -= 1
                if curr_window[tree[l]] == 0:
                    del curr_window[tree[l]]
                l += 1
                                    
            if r - l + 1 > res:
                res = r - l + 1
                
            r += 1
                
        
        return res
        
        


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        ans = i = 0
        count = collections.Counter()
        for j, x in enumerate(tree):
            count[x] += 1
            while len(count) > 2:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i += 1
            ans = max(j - i + 1, ans)
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        last_fruit = -1
        second_last_fruit = -1
        last_fruit_count = 0
        current_max = 0
        maxi = 0
        
        for fruit in tree:
            if fruit == last_fruit or fruit == second_last_fruit:
                current_max+=1
            else:
                current_max = last_fruit_count + 1
                
            if fruit == last_fruit:
                last_fruit_count += 1
            else:
                last_fruit_count = 1
                
            if fruit != last_fruit:
                second_last_fruit = last_fruit
                last_fruit = fruit
                
            
            maxi = max(current_max, maxi)
            
        return maxi

from collections import Counter
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        res = l = 0
        count = Counter()
        for r, t in enumerate(tree):
            count[t] += 1
            while len(count) >= 3:
                count[tree[l]] -= 1
                if count[tree[l]] == 0:
                    del count[tree[l]]
                l += 1
            res = max(res, r - l + 1)
        return res

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        max_length = 0
        fruits_frequency = defaultdict(int)
        window_start = 0
        
        for window_end in range(0, len(tree)):
            right_fruit = tree[window_end]
            fruits_frequency[right_fruit] += 1
            
            while len(fruits_frequency) > 2:
                left_fruit = tree[window_start]
                fruits_frequency[left_fruit] -= 1
                if fruits_frequency[left_fruit] == 0:
                    del fruits_frequency[left_fruit]
                    
                window_start += 1
            max_length = max(max_length, window_end - window_start + 1)
            
        return max_length

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        count2 = 0
        basket = 0
        ans = 0
        kind1, kind2 = 0, 0
        for t in tree:
            if t == kind2:
                count2 += 1
                basket += 1
            elif t == kind1:
                count2 = 1
                basket += 1
                kind1, kind2 = kind2, kind1
            else:
                basket = count2 + 1
                count2 = 1
                kind1, kind2 = kind2, t
            ans = max(ans, basket)
        return ans


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        left=ans=0
        types=collections.defaultdict(int)
        for right in range(len(tree)):
            types[tree[right]]+=1
            if len(types.keys())<=2:
                ans=max(ans,right-left+1)
            while len(types.keys())>2:
                types[tree[left]]-=1
                if types[tree[left]]==0:
                    types.pop(tree[left])
                left+=1
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        l, r, ans = 0, 0, 0
        counter = Counter()
        length = 0
        while r < len(tree):
            counter[tree[r]] += 1
            length = len(counter)
            r += 1

            while length > 2:
                counter[tree[l]] -= 1
                if counter[tree[l]] == 0:
                    del counter[tree[l]]
                    length -= 1
                l += 1
            ans = max(ans, r - l)
        return ans






class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        maxStreak = 0
        i = 0
        types = set()
        last_type = 0
        streak = 0
        while i < len(tree):
            if len(types) == 0 or len(types) == 1:
                types.add(tree[i])
                last_type = i
                streak += 1
                i += 1
            else:
                if tree[i] in types:
                    if tree[last_type] != tree[i]:
                        last_type = i
                    streak += 1
                    i += 1
                else:
                    i = last_type
                    types = set()
                    maxStreak = max(streak, maxStreak)
                    streak = 0
                    
        return max(streak, maxStreak)


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        cnt = 1
        max = 1
        keys = set([tree[0]])
        
        spree = [tree[0], 1] # to hold the numberof fruits before a switch
        
        for k in range(1, len(tree)):
            if tree[k] in keys:
                cnt += 1
                if tree[k] == spree[0]:
                    spree[1] +=1
                else:
                    spree = [tree[k], 1]
            elif len(keys)==1: # if the 1st tree is the same as the following...
                keys.add(tree[k])
                cnt +=1
                spree = [tree[k], 1]
            else:
                if cnt > max:
                    max = cnt
                keys = set([tree[k-1], tree[k]])
                cnt = spree[1] + 1 #reset counter
                spree = [tree[k], 1]
  
        if cnt > max:
            max = cnt
        return max

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        start = 0
        end = 1
        maxLength = 1
        types = {}
        types[tree[0]] = 1
        
        if len(tree) <= 2:
            return len(tree)
        
        while end < len(tree) - 1 or start < end:
            if end < len(tree)-1 and len(types) < 2:                
                if types.get(tree[end]):
                    types[tree[end]] += 1
                else:
                    types[tree[end]] = 1
                
                end += 1
            elif end == len(tree) or types.get(tree[end]) == None:
                types[tree[start]] -= 1
                
                if types[tree[start]] == 0:
                    del types[tree[start]]
                
                start += 1           
            else:                
                if types.get(tree[end]):
                    types[tree[end]] += 1
                else:
                    types[tree[end]] = 1
                    
                end += 1
                
            if len(types) <= 2:
                maxLength = max(maxLength, end-start)
            
        return maxLength

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if(len(tree)<=1):
            return len(tree)
        if(len(list(set(tree))) == 2):
            return len(tree)
        maxCount = 0
        classes = []
        i = 0
        while(i < len(tree)):
            j = i + 1
            classes = [tree[i]]
            count = 1
            secFruitStart = -1
            while(len(classes) <= 2 and j < len(tree)):
                if(tree[j] not in classes):
                    classes.append(tree[j])
                    if(len(classes) == 2):
                        secFruitStart = j
                if(len(classes) == 3):
                    continue
                count = count + 1
                j = j + 1
            if(count > maxCount):
                maxCount = count
            if(secFruitStart != -1):
                i = secFruitStart
            else:
                break
        return maxCount

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        #max contiguous sum with 2 different types of elements
        
        start = 0
        end = 0
        le = len(tree)
        hmap = collections.defaultdict(int)
        count = 0
        res = 0
        
        while end < le:
            
            hmap[tree[end]] += 1
            if hmap[tree[end]] == 1:
                count += 1
            
            end += 1
            
            while count > 2 and start < end:
                hmap[tree[start]] -= 1
                if hmap[tree[start]] == 0:
                    count -= 1
                start += 1
            
            if count > 2:
                continue
            
            res = max(res, end-start)
        
        return res
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        secondLastFruit = -1
        lastFruit = -1
        lastFruitCount = 0
        currFruits = 0
        maxFruits = 0
        
        for fruit in tree:
            if fruit == lastFruit or fruit == secondLastFruit:
                currFruits += 1
            else:
                currFruits = lastFruitCount + 1
                
            if fruit == lastFruit:
                lastFruitCount += 1
            else:
                lastFruitCount = 1
                secondLastFruit = lastFruit
                lastFruit = fruit
                
            maxFruits = max(currFruits, maxFruits)
        
        return maxFruits

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        i,maxLen=0,0
        cache=collections.defaultdict(int)
        for j in range(len(tree)):
            cache[tree[j]]+=1
            if len(cache)<=2:
                maxLen=max(maxLen,j-i+1)
            while len(cache)>2:
                cache[tree[i]]-=1
                if cache[tree[i]]==0:
                    del cache[tree[i]]
                i+=1
        if maxLen==0:
            return 1
        return maxLen



class Solution:
    def totalFruit(self, tree) -> int:
        '''

        :param tree: : List[int]
        :return:
        '''
        n = len(tree)
        if n <=2:
            return n 
        tem = collections.Counter()
        res = 0
        i = 0
        j = 1
        tem.update(tree[:1])

        while j<n:
            while j < n and  len(tem.keys()) <=2:
                tem.update([tree[j]])
                res = max(res, j - i )
                j += 1

            while len(tem.keys()) >=3 :
                tem[tree[i]] -= 1
                if tem[tree[i]] ==0:
                    tem.pop(tree[i])
                i += 1

            if j == n :
                res = max(res, j - i)
                break
        return res

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        res = 0
        
        mres = 0
        temp = set()
        i = 0
        newidx = 0
        
        while i < len(tree):
            if len(temp) == 0:
                mres += 1
                temp.add(tree[i])
                i += 1
            
            elif len(temp) == 1:
                newidx = i
                temp.add(tree[i])
                mres += 1
                i += 1
                
            else:
                if tree[i] in temp:
                    mres += 1
                    i += 1
                else:
                    res = max(res, mres)
                    mres = 0
                    temp = set()
                    i = newidx
                    
        res = max(res, mres)
        return res
            
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if not tree:
            return 0
        if len(set(tree)) <= 2:
            return len(tree)
        
        max_collected = 0
        
        for i in range(len(tree)):
            num_collected = 0
            different_types = set()
            for j in range(i, len(tree)):
                if len(different_types) < 2:
                    different_types.add(tree[j])
                    num_collected += 1
                elif tree[j] in different_types:
                    num_collected += 1
                else:
                    break
            
            max_collected = max(max_collected, num_collected)
        
        return max_collected

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
      item1_val = -1
      item1_fs = -1 
      item1_ls = -1
      item2_val = -1
      item2_fs = -1
      item2_ls = -1
      size = list()
      for i in range(len(tree)):
        if tree[i] == item1_val:
          item1_ls = i
          if item1_fs == -1:
            item1_ls = i
          if i == 0:
            size.append(1)
          size.append(size[i-1] + 1)
        elif tree[i] == item2_val:
          item2_ls = i
          if item2_fs == -1:
            item2_ls = i
          if i == 0:
            size.append(1)
          size.append(size[i-1] + 1)
        else:
          if item1_ls > item2_ls: # item1 stays
            item1_fs = item2_ls + 1
            item2_val = tree[i]
            item2_fs = i
            item2_ls = i
            size.append(i - item1_fs + 1)
          else: # item2 stays
            item2_fs = item1_ls + 1
            item1_val = tree[i]
            item1_fs = i
            item1_ls = i
            size.append(i - item2_fs + 1)

      return(max(size))


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        counter = collections.defaultdict(int)
        
        start = 0
        res = 0
        
        for end in range(len(tree)):
            counter[tree[end]] += 1
            
            while len(list(counter.keys())) > 2:
                counter[tree[start]] -= 1
                
                if counter[tree[start]] == 0:
                    del counter[tree[start]]
                
                start += 1
            res = max(res, sum(counter.values()))
        
        return res
            
            
                



from collections import defaultdict
class Solution:
    def totalFruit(self, tree):
        if len(tree) <3:
            return len(tree)
        # run1 = 0
        # run2 = 1
        # # run3 = 0
        best_pair = 0
        # tree_type1 = None
        # tree_type2 = tree[0]
        forest = defaultdict(int)
        forest[tree[0]] = (0,1)
        for t in range(1, len(tree)):
            # print('tree',t)
            if tree[t] not in forest:
                best_pair = max([best_pair, sum([b for basket in list(forest.values()) for b in basket])])
                temp = defaultdict(int)
                temp[tree[t]] = (0,0)
                temp[tree[t-1]] = (0,forest[tree[t-1]][-1])
                forest = temp
                # print('established tt1', t)
            if tree[t] == tree[t-1]:
                forest[tree[t]] = (forest[tree[t]][0],forest[tree[t]][-1]+1)
            else:
                # print(forest)
                forest[tree[t]] = (sum(forest[tree[t]]),1)
            # if t == tree_type1:
            #     run1 += 1
            #     print('run1',run1)
            # elif t == tree_type2:
            #     run2 += 1
            #     print('run2', run2)
            # else:
            #     print('new set')
            #     best_pair = max([best_pair, sum([run1, run2])])
            #     run2 = run1
            #     run1 = 1
            #     tree_type2 = tree_type1
            #     tree_type1 = t
            #     print(best_pair, run1, run2, 'tree_type1',tree_type1,'tree_type2', tree_type2)
            # print(run1, run2)
            # print(forest)
            # print(best_pair)
        best_pair = max([best_pair, sum([b for basket in list(forest.values()) for b in basket])])
        return best_pair


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        c = collections.Counter()
        j = 0
        ans = 0
        for i in range(len(tree)):
            c[tree[i]]+=1
            while len(c)>=3:
                c[tree[j]] -= 1
                if c[tree[j]]==0:
                    del c[tree[j]]
                j+=1
            ans = max(ans,i-j+1)
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        prev_count = curr =  count_b = result = 0
        a = None
        b = None
        for c in tree:
            if b == c:
                curr += 1
                count_b += 1
            elif a == c:
                curr += 1
                count_b = 1
                a = b
                b = c
            elif a != c and b != c:
                curr = count_b + 1
                count_b = 1
                a = b
                b = c
            result = max(result, curr)
        return result

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        current_picking = tree[0]
        prev_picking = None
        max_picked = 0
        baskets = {current_picking: [0, 0]}
        for i in range(len(tree)):
            if tree[i] != current_picking:
                if len(baskets) < 2:
                    baskets[current_picking] = [0, i-1]
                    prev_picking = current_picking
                    current_picking = tree[i]
                    baskets[current_picking] = [i, i]
                else:
                    if tree[i] != prev_picking:
                        baskets = {
                            current_picking: [baskets[prev_picking][1] + 1, baskets[current_picking][1]],
                            tree[i]: [i, i]
                        }
                        prev_picking = current_picking
                        current_picking = tree[i]
                    else:
                        prev_picking, current_picking = current_picking, prev_picking
                        baskets[current_picking][1] = i
            else:
                baskets[current_picking][1] = i
            if baskets.get(current_picking) and baskets.get(prev_picking):
                max_picked = max(max_picked, max([pos[1] for pos in baskets.values()]) - min([pos[0] for pos in baskets.values()]) + 1)
            else:
                max_picked = max(max_picked, baskets[current_picking][1] - baskets[current_picking][0] + 1)
        return max_picked

from collections import Counter
class window:
    
    def __init__(self):
        self.type = Counter()
    
    def add(self, x):
        self.type[x] += 1
    
    def remove(self, x):
        self.type[x] -= 1
        if self.type[x] == 0:
            del self.type[x]
    
    def valid(self):
        return len(self.type) <= 2
        
        
class Solution:
    def totalFruit(self, tree):
        
        win = window()
        l, res = 0, 0
        for r,fruit in enumerate(tree):
            win.add(fruit)
            while l < r and not win.valid():
                win.remove(tree[l])
                l += 1
            res = max(res, r-l+1)
        return res
            
            
        
        
        
        


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if not tree:
            return 0
        
        n = len(tree)
        res = 1
        
        # starting type
        last_occur = {tree[0]: 0}
        
        i, j = 0, 1
        
        # condition for while loop
        while j < n:
            new_type = tree[j]
            if new_type in last_occur or len(last_occur.keys()) < 2:
                last_occur[new_type] = j
                res = max(res, j-i+1)
                
            # should have new types
            else:
                count = j - i
                res = max(res, count)
                
                # start from the new index
                keys = list(last_occur.keys())
                t = keys[0] if last_occur[keys[0]] < last_occur[keys[1]] else keys[1]
                i = last_occur[t] + 1
                del last_occur[t]
                # new starting type at i
                
                last_occur[new_type] = j

            j+=1

        return res

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        maxL = 0
        l, r = 0, 0 # 0, 4
        if len(set(tree)) < 3:
            return len(tree)
        
        while r <= len(tree):
            temp = tree[l:r]
            if len(set(temp)) < 3:
                maxL = max(maxL, len(temp))
                r += 1
            elif len(set(temp)) >= 3:
                l += 1
        
        return maxL

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        #two fruit
        firstFruit = secondFruit = -1
        firstQuant = secondQuant = 0
        ans = 0
        
        n = len(tree)
        i = 0
        while i<n:
            if firstQuant == 0 or firstFruit == tree[i]:
                firstFruit  = tree[i]
                firstQuant += 1
            elif secondQuant == 0 or secondFruit == tree[i]:
                secondFruit = tree[i]
                secondQuant += 1
            
            elif i>0 and tree[i-1] == firstFruit:
                secondFruit = tree[i]
                secondQuant = 1
                j = i-1
                while j>=0 and tree[j]==firstFruit:
                    j-=1
                firstQuant = i-1-j
                    
            elif i>0 and tree[i-1] == secondFruit:
                firstFruit = tree[i]
                firstQuant = 1
                j = i-1
                while j>=0 and tree[j]==secondFruit:
                    j-=1
                secondQuant = i-1-j
            ans = max(ans,firstQuant+secondQuant)
            #print(firstFruit,firstQuant,secondFruit,secondQuant,ans)
            i+=1
        return ans


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        ans = i = 0
        count = collections.Counter()
        # count = {}
        for j, x in enumerate(tree):
            count[x] += 1
            # if x not in count:
            #     count[x] = 1
            # else:
            #     count[x] += 1
            while len(count) == 3:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans
            
            


class Solution:
    def totalFruit(self, ar: List[int]) -> int:
        l=list(set(ar))
        if len(l)<=2:
            return len(ar)
        else:
            m=0
            for i in range(0,len(ar)):
                l=[ar[i]]
                # c=0
                d=1
                for j in range(i+1,len(ar)):
                    if ar[j] in l:
                        l.append(ar[j])
                    elif ar[j] not in l and d==1:
                        d+=1
                        l.append(ar[j])
                    else:
                        break
                m=max(m,len(l))
            return m
                    
                    
                
               
        
        


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if len(tree)==1:
            return 1
        
        window_start = 0
        window_end = 2
        total_max = 2
        
        if tree[0] == tree[1]:
            tmp_index = 0
        else:
            tmp_index = 1
            
        fruit_type = set(tree[:2])
        
        for i in range(2, len(tree)):
            if (tree[i] in  fruit_type) or len(fruit_type)<2:
                window_end += 1
                if tree[i] != tree[i-1]:
                    tmp_index = i
                fruit_type.add(tree[i])
            else:
                window_start  = tmp_index
                tmp_index = i
                window_end += 1
                fruit_type = set(tree[i-1:i+1])
            #print(window_start, window_end, fruit_type)
            if window_end - window_start > total_max:
                total_max = window_end - window_start
        return total_max


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        dp = [[] for i in range(len(tree))]
        dp[-1] = [1, 1, [tree[-1]]]
        res = 1
        for i in reversed(list(range(len(tree)-1))):
            if tree[i] == tree[i+1]:
                dp[i] = [dp[i+1][0]+1, dp[i+1][1]+1, dp[i+1][2]]
            elif len(dp[i+1][2]) == 1:
                dp[i] = [dp[i+1][0]+1, 1, [tree[i], dp[i+1][2][0]]] 
            elif tree[i] in dp[i+1][2]:
                dp[i] = [dp[i+1][0]+1, 1, dp[i+1][2]]
            else:
                dp[i] = [1+dp[i+1][1], 1, [tree[i], tree[i+1]]]
            res = max(res, dp[i][0])
        return res


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        N = len(tree)
        out = 0
        start = 0
        olderstart = 0
        newerend = newerstart = 0
        olderend = olderstart = 0
        older = newer = tree[0]        
        j = 0
        if N < 3:
            return len(tree)
        while newer == older and j < N:
            olderend = j
            j+= 1
            if j == N:
                return N
            newer = tree[j]
            newerstart = j
            
        assert(newer != older)
        
        for i in range(j, N):
            curr = tree[i]
            if (curr == older or curr == newer) :
                if curr == older:
                    olderend = i
                if curr == newer:
                    newerend = i
                
            else:
                
                if prev == older:
                    olderstart = newerend+1
                else:                    
                    olderstart = olderend+1
                    olderend = newerend
                    older = newer                   
                
                newerstart = i
                newerend = i
                newer = curr
                
            prev = curr                
            out = max(i-olderstart+1, out)
        return out
                
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        i = 0
        count = collections.Counter()
        for value in tree:
            count[value] += 1
            if len(count) > 2:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i +=1
        return len(tree) - i


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if len(tree)<=2: return len(tree)
        
        n = len(tree)
        
        res = 0 
        start = 0
        while start<n:
            type1, type2, type2_pos = -1, -1, -1
            i = start 
            while i<n: # i represents the end pos
                if type1 == -1:
                    type1 = tree[i]
                    
                elif tree[i]!=type1 and type2 == -1:
                    type2 = tree[i]
                    type2_pos = i
                    
                elif tree[i]!=type1 and tree[i]!=type2:
                    break
                i += 1
                
            res = max(res, i-start)
            if i==n: break
            start = type2_pos
            
        return res
            
                
        
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        total_len = len(tree)
        
        if total_len == 0:
            return 0
        
        rst = 1
        
        fruit_1 = tree[0]
        
        start = 0
        
        # Check the first fruit
        while tree[start] == fruit_1:
            start += 1
            if start >= total_len:
                return start
        
        # Check the second fruit
        fruits = [fruit_1, tree[start]]
        fruits_order = [start-1, start]
        total_fruits = start+1
        
        #print(fruits, fruits_order, total_fruits, start)
        
        for i in range(start+1, total_len):
            #print(\"new_fruit is\", tree[i])
            if tree[i] == fruits[0]:
                fruits_order[0] = i
                total_fruits += 1
                #print(\"Update the basket 0\", fruits, fruits_order, total_fruits)
                
            elif tree[i] == fruits[1]:
                fruits_order[1] = i
                total_fruits += 1
                #print(\"Update the basket 1\", fruits, fruits_order, total_fruits)
                
            else:
                if total_fruits > rst:
                    rst = total_fruits
                if fruits_order[0] > fruits_order[1]:
                    fruits[1] = tree[i]
                    total_fruits = i - fruits_order[1]
                    fruits_order[1] = i
                else:
                    fruits[0] = tree[i]
                    total_fruits = i - fruits_order[0]
                    fruits_order[0] = i
                
                #print(\"generate the new fruits order, type\")
                #print(fruits, fruits_order, total_fruits)
                
        if total_fruits > rst:
            return total_fruits
        
        return rst
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
    
        out = 0
        for i in range(len(tree)):
            tot = self.getTotalAtIndex(tree, i)
            if tot>out:
                out = tot
            if tot == len(tree):
                break
        return out
    
    
    def getTotalAtIndex(self, tree, i):
        
        fruit_types = set()
        cnt = 0
        for j in range(i, len(tree)):
            if len(fruit_types)<2:
                fruit_types.add(tree[j])
                
            if tree[j] in fruit_types:
               cnt+=1
            else:
                break
        return cnt
        pass


from collections import defaultdict
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        st = 0
        max_len = 0
        basket = defaultdict(int)

        for end in range(len(tree)):
            basket[tree[end]] += 1

            while len(basket) > 2:
                basket[tree[st]] -= 1
                if basket[tree[st]] == 0:
                    del basket[tree[st]]
                st += 1

            total = 0
            for k in basket:
                total += basket[k]

            max_len = max(max_len, total)

        return max_len


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        n = len(tree)
        
        if n < 3:
            return n
        
        max_count = 0

        dp = [[set(),0,set(),0] for _ in range(n)]
        
        dp[0] = [{tree[0]},1,{tree[0]},1]
        
        for i in range(1, n):
            if tree[i] in dp[i-1][2]:
                set_2 = dp[i-1][2].copy()
                count_2 = dp[i-1][3] + 1
            else:
                temp = dp[i-1][0].copy()
                temp.add(tree[i])
                set_2 = temp
                count_2 = dp[i-1][1] + 1
            if tree[i] in dp[i-1][0]:
                set_1 = dp[i-1][0].copy()
                count_1 = dp[i-1][1] + 1
            else:
                set_1 = {tree[i]}
                count_1 = 1
                
            dp[i] = [set_1, count_1, set_2, count_2]
            
            max_count = max(max_count, max(count_1, count_2))
            
            
        return max_count
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        count = collections.Counter()
        i = ans = 0

        for j in range(len(tree)):
            fruit = tree[j]
            count[fruit] += 1

            while len(count.keys()) > 2:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i += 1

            ans = max(ans, j-i+1)

        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if len(tree) <= 2:
            return len(tree)
        types = {tree[0]: 0, tree[1]: 1} if tree[0] != tree[1] else {tree[0]: 1}
        res = 2
        temp = 2
        for i in range(2, len(tree)):
            if len(types) == 2:
                if tree[i] not in types:
                    res = max(res, temp)
                    delete = sorted(types, key=types.get)[0]
                    temp = i - types[delete]
                    del types[delete]
                    types[tree[i]] = i
                else:
                    temp += 1
                    types[tree[i]] = i
            else:
                temp += 1
                types[tree[i]] = i
        res = max(res, temp)
        return res

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        ans = i = 0
        count = collections.Counter()
        for j, x in enumerate(tree):
            count[x] += 1
            while len(count) >= 3:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans
            
        
            
        
        


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        left_pointer, right_pointer = 0, 0
        fruits = 0
        fruits_in_basket = {}
        
        while (right_pointer < len(tree)) :
            if (len(fruits_in_basket) <= 2) :
                fruits_in_basket[tree[right_pointer]] = right_pointer
                right_pointer += 1
                #print(fruits_in_basket)
            if (len(fruits_in_basket) > 2) :
                minimum_index = len(tree)
                for index in list(fruits_in_basket.values()) :
                    minimum_index = min(minimum_index, index)
                left_pointer = minimum_index + 1
                #print(left_pointer)
                fruits_in_basket.pop(tree[minimum_index])
            fruits = max(fruits, (right_pointer - left_pointer))
            #print(fruits)
            
        return fruits


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if tree == [] or tree is None:
            return 0
        
        if len(tree) == 1:
                return 1

        # [1,3,3,1]
        s = 0
        max = 1
        count = max
        
        for i in range(len(tree)):
            j = i + 1
            b1 = tree[i]  # backet 1
            b2 = tree[j]  # backet 2
            count = 1

            if b1 == b2:
                # continue finding a different value while incrementing
                while j < len(tree) and tree[j] == b1:
                    j += 1
                    count += 1
                if j != len(tree):
                    b2 = tree[j]    
                elif count > max:
                    return count
            
            while j < len(tree):
                
                
                    
                # a new number occured
                if tree[j] != b1 and tree[j] != b2:
                    # compare count and max
                    if count >= max:
                        max = count
                    # reset starting position
            
                    break
                
                # pick up fruit and move
                count += 1
                j += 1

                if j == len(tree):
                    if count >= max:
                        max = count
                    return max
                
        return max
          


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        char_to_count = defaultdict(int)
        unique_chars = 0
        
        start = 0
        end = 0
        max_fruit = 0
        while end < len(tree):
            char_to_count[tree[end]] += 1
            if char_to_count[tree[end]] == 1:
                unique_chars +=  1
            
            while unique_chars > 2:
                char_to_count[tree[start]] -= 1
                if char_to_count[tree[start]] == 0:
                    unique_chars -= 1
                start += 1
            end += 1
            max_fruit = max(max_fruit, end-start)
            
        return max_fruit


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        d = {}
        first = -1
        second = -1
        i = 0
        n = len(tree)
        m = -1
        while i<n:
            if tree[i] in d:
                d[tree[i]].append(i)
                i+=1
            else:
                if len(list(d.keys()))==2:
                    s = 0
                    for k,v in list(d.items()):
                        s+=len(v)
                    m = max(m, s)
                    if d[first][-1]>d[second][-1]:
                        i = d[second][-1]+1
                        first = first
                        d = {}
                        d[tree[i]] = [i]
                        i+=1
                    else:
                        i = d[first][-1]+1
                        first = second
                        d = {}
                        d[tree[i]] = [i]
                        i+=1
                elif len(list(d.keys()))==1:
                    second = tree[i]
                    d[tree[i]] = [i]
                    i+=1
                else:
                    first = tree[i]
                    d[tree[i]] = [i]
                    i+=1
        s = 0
        for k,v in list(d.items()):
            s+=len(v)
        return max(m, s)
                    
                    
            
                
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        a = Counter(tree)
        if len(a) <= 2:
            return len(tree)
        
        ans = 0
        
        i = 0
        while i < len(tree):
            count = 1
            basket = [tree[i]]
            j = i + 1
            while j < len(tree):
                if tree[j] in basket:
                    count += 1
                else:
                    if len(basket) >= 2:
                        break
                    else:
                        basket.append(tree[j])
                        count += 1
                j += 1
            
            if count > ans:
                ans = count
            i += 1
            
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        if len(set(tree))<=2:
            return len(tree)
        
        types = set()

        maxFruits = 0
        
        for i in range(len(tree)):
            start = i
            res = 0
            types = set()
            for i in range(start,len(tree)):
                fruitType = tree[i]
                if (len(types)>=2) and (fruitType not in types):
                    break
                elif fruitType in types:
                    res+=1
                else:
                    types.add(fruitType)
                    res+=1
            
            maxFruits = max(maxFruits,res)
            
        return maxFruits

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        dic = {}
        first = 0
        i = 0
        n = len(tree)
        ans = 0
        while i<n:
            val = tree[i]
            if val in dic:
                dic[val] += 1
            elif len(dic)<2: 
                dic[val] = 1
            else:
                dic[val] = 1
                while len(dic) >= 2:
                    v2 = tree[first]
                    first+=1
                    dic[v2] -= 1
                    if dic[v2] == 0:
                        dic.pop(v2,None)
                        break
            ans = max(i-first+1, ans)
            i+=1
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        fruits = tree
        window_start = 0
        max_length = 0
        fruit_frequency = {}

  # try to extend the range [window_start, window_end]
        for window_end in range(len(fruits)):
            right_fruit = fruits[window_end]
            if right_fruit not in fruit_frequency:
                fruit_frequency[right_fruit] = 0
            fruit_frequency[right_fruit] += 1

    # shrink the sliding window, until we are left with '2' fruits in the fruit frequency dictionary
            while len(fruit_frequency) > 2:
                left_fruit = fruits[window_start]
                fruit_frequency[left_fruit] -= 1
                if fruit_frequency[left_fruit] == 0:
                    del fruit_frequency[left_fruit]
                window_start += 1  # shrink the window
            max_length = max(max_length, window_end-window_start + 1)
        return max_length    

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        best_attempt = 0
        for i in range(len(tree)):
            baskets = {}
            for j in range(i, len(tree)):
                if tree[j] in baskets:
                    baskets[tree[j]] += 1
                elif len(baskets) >= 2:
                    break
                else:
                    baskets[tree[j]] = 1
            attempt_val = sum(baskets.values())
            if attempt_val > best_attempt:
                best_attempt = attempt_val
            if best_attempt > len(tree) - i:
                break
        return best_attempt
        


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        res = 0
        N = len(tree)
        oneidx = twoidx = 0
        onetype = tree[0]
        twotype = None
        left, right = 0, 0
        while right < N and tree[right] == onetype:
          oneidx += 1
          right += 1
        oneidx -= 1
        if right == N:
          return N
        twotype = tree[right]
        twoidx = right
        while right < N:
          if tree[right] == onetype:
            oneidx = right
          elif tree[right] == twotype:
            twoidx = right
          else:
            res = max(res, right - left)
            if oneidx < twoidx:
              left = oneidx + 1
              onetype = tree[right]
              oneidx = right
            else:
              left = twoidx + 1
              twotype = tree[right]
              twoidx = right
          right += 1
        return max(res, right - left)


from collections import OrderedDict

class Solution:
    
    def totalFruit(self, tree: List[int]) -> int:
        
        last_index_of = OrderedDict()
        
        ans = l = 0
        
        for i, t in enumerate(tree):
            
            last_index_of[t] = i
            last_index_of.move_to_end(t)
            
            if len(last_index_of) > 2:
                ans = max(ans, i-l)
                l = last_index_of.popitem(last=False)[1] + 1
                
        ans = max(ans, len(tree) - l)
        
        return ans

'''
{3:1,1:1}

'''
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        first,sec=0,0
        curr_hash={}
        if len(tree)<3:return len(tree)
        Max=[float('-inf')]
        while(first<len(tree)):
            first=self.first_pass(first,curr_hash,tree,Max)
            if first>len(tree):continue
            sec=self.sec_pass(sec,first,curr_hash,tree)
        return Max[0]
    def first_pass(self,pointer,hash,trees,Max):
        count=0
        for key in hash:
            count+=hash[key]
        while(pointer<len(trees)):
            typ=trees[pointer]
            if typ in hash:hash[typ]+=1
            else:
                if len(hash)<2:
                    hash[typ]=1
                else:
                    break
            count+=1
            pointer+=1
        Max[0]=max(Max[0],count)
        return pointer
    
    def sec_pass(self,sec,first,hash,tree):
        while(sec<first and len(hash)>1):
            typ=tree[sec]
            if hash[typ]==1: del hash[typ]
            else: hash[typ]-=1
            sec+=1
        return sec
        


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        if len(set(tree))<=2:
            return len(tree)
        
        types = set()

        maxFruits = 0
        
        for i in range(len(tree)):
            start = i
            res = 0
            types = set()
            
            if (len(tree)-start)<=maxFruits:
                continue
            
            for i in range(start,len(tree)):
                fruitType = tree[i]
                if (len(types)>=2) and (fruitType not in types):
                    break
                elif fruitType in types:
                    res+=1
                else:
                    types.add(fruitType)
                    res+=1
            
            maxFruits = max(maxFruits,res)
            
        return maxFruits

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        k = 2
        left = 0
        cnt = collections.Counter()
        res = 0
        for j, i in enumerate(tree):
            if cnt[i] == 0: k-=1
            cnt[i] += 1
            while k<0:
                cnt[tree[left]] -= 1
                if cnt[tree[left]] == 0: k+=1
                left += 1
            res = max(res, j-left +1)
        return res
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        c=0
        p=0
        for i in range(len(tree)):
            l=[]
            k=0
            for j in range(i,len(tree)):
                if(tree[j] not in l):
                    l.append(tree[j])
                    k+=1
                else:
                    k+=1
                #print(l)
                if(len(l)>2):
                    k=k-1
                    break
               
            if(k>p):
                p=k
            if(p==len(tree)):
                break;
        return p
                    
                    
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        max_count = 0
        tree_len = len(tree)
        if len(tree) == 1:
            return 1
        if len(set(tree)) in (1,2):
            return len(tree)
        for i in range(tree_len - 1):
            tree_set = set()
            tree_set.add(tree[i])
            count = 1
            for j in range(i+1, tree_len):
                if tree[j] not in tree_set and len(tree_set) == 2:
                    break
                tree_set.add(tree[j])
                count += 1
            max_count = max(max_count, count)
        return max_count
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        blocks = [(k, len(list(v)))
                  for k, v in itertools.groupby(tree)]

        ans = i = 0
        while i < len(blocks):
            # We'll start our scan at block[i].
            # types : the different values of tree[i] seen
            # weight : the total number of trees represented
            #          by blocks under consideration
            types, weight = set(), 0

            # For each block from i and going forward,
            for j in range(i, len(blocks)):
                # Add each block to consideration
                types.add(blocks[j][0])
                weight += blocks[j][1]

                # If we have 3 types, this is not a legal subarray
                if len(types) >= 3:
                    i = j-1
                    break

                ans = max(ans, weight)

            # If we go to the last block, then stop
            else:
                break

        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        st = c = res = 0
        dic = dict()
        for end in range(len(tree)):
            if tree[end] in dic:
                dic[tree[end]] += 1
            else:
                dic[tree[end]] = 1
                c += 1
            while c > 2:
                dic[tree[st]] -= 1
                if dic[tree[st]] == 0: 
                    del dic[tree[st]]
                    c -= 1
                st+=1
            res = max(res,end-st+1)
        return res


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        insp = {}
        pos = {}
        mxx = -1
        i = 0
        while i < len(tree):
            f = tree[i]
            if f not in insp and len(insp) == 2:
                mnn = math.inf
                tod = None
                for of, op in list(pos.items()):
                    mnn = min(mnn, op)
                    if mnn == op:
                        tod = of
                k = pos[tod]
                while k >= 0:
                    of = tree[k]
                    if of not in pos:
                        break
                    insp[of] -= 1
                    k -= 1
                        
                del pos[tod]
                del insp[tod]
                insp[f] = 0
            elif f not in insp:
                insp[f] = 0
            
            pos[f] = i
            insp[f] += 1
            score =  self.get_basketsize(insp)
            mxx = max(mxx,score)
            i += 1
            
        return mxx
          
    def get_basketsize(self, insp):
        mxx = 0
        nmxx = 0
        for f,ct in list(insp.items()):
            if ct >= mxx:
                nmxx = max(mxx, nmxx)
                mxx = max(ct, mxx)
            elif ct >= nmxx:
                nmxx = max(ct, nmxx)
        return mxx + nmxx


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        counter = collections.Counter()
        
        l = r = 0
        res = 0
        while r < len(tree):
            counter[tree[r]] += 1
            while len(counter.keys()) > 2:
                counter[tree[l]] -= 1
                if counter[tree[l]] == 0:
                    del counter[tree[l]]
                l += 1
            res = max(res, sum(counter.values()))
            r += 1
        return res

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        start = end = disFruits = curTotal = maxTotal = 0
        fruits = {}
        while end < len(tree):
            curFruit = tree[end]
            frontFruit = tree[start]
            if curFruit not in fruits and disFruits == 2:
                if fruits[frontFruit] == 1:
                    del fruits[frontFruit]
                    disFruits -= 1
                else:
                    fruits[frontFruit] -= 1
                curTotal -= 1
                start += 1
            else:
                curFruit = tree[end]
                if curFruit not in fruits:
                    fruits[curFruit] = 1
                    disFruits += 1
                else:
                    fruits[curFruit] += 1
                curTotal += 1
                maxTotal = max(curTotal, maxTotal)
                end += 1
        return maxTotal
                        
            
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if len(tree) == 1:
            return 1
        start = last1 = last2 = 0
        res = 1
        for i in range(1, len(tree)):
            if tree[i] == tree[last1]:
                last1 = i
            elif tree[i] == tree[last2]:
                last2 = i
            elif tree[last1] == tree[last2]:
                last1 = max(last1, last2)
                last2 = i
            else:
                start = min(last1, last2)+1
                if last1 < last2:
                    last1 = i
                else:
                    last2 = i
            res = max(res, i-start+1)
        return res


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
           
        ans = i = 0
        count = collections.Counter()
        for j, x in enumerate(tree):
            count[x] += 1
            while len(count) >= 3:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        def pick(start, end):
            res = 0
            fruitType = set()
            
            for i in range(start, end):
                fruit  = tree[i]
                if fruit not in fruitType and len(fruitType) >= 2:
                    return res
                
                fruitType.add(fruit)
                res += 1
            
            return res
        
        ##Main
        n = len(tree)
        cnt = Counter(tree)
        if len(cnt) <= 2:
            return n
        
        maxFruit = 0
        for i in range(n):
            maxFruit = max(maxFruit, pick(i, n))
            
        return maxFruit

from collections import defaultdict

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        counter = {}
        longest = 0
        fruits = 0
        i = 0
        for j in range(len(tree)):
            if tree[j] not in counter:
                fruits += 1
                counter[tree[j]] = 0
            counter[tree[j]] += 1
            while fruits > 2:
                counter[tree[i]] -= 1
                if counter[tree[i]] == 0:
                    fruits -= 1
                    del counter[tree[i]]
                i += 1
            longest = max(longest, j-i+1)
        return longest

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if(len(tree)==1):
            return 1
        if(not tree):
            return 0
        i = 0
        j = 1
        l=len(tree)
        ans=0
        found = False
        second = tree[1]
        count = 1
        while(i<l and j<l):
            if(tree[i]!=tree[j] and not found):
                second=tree[j]
                found=True
            if(found and tree[j]!=second and tree[j]!=tree[i]):
                ans=max(ans,count)
                count=0
                i+=1
                j=i
                found=False
            j+=1
            count+=1
        ans=max(ans, count)
        return ans


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        fruit_dict = collections.defaultdict(int)
        j,result,count=0,0,0
        for i,t in enumerate(tree):
            fruit_dict[t]+=1
            count+=1
            while len(fruit_dict)>2 and j<len(tree):
                fruit_dict[tree[j]]-=1
                count-=1
                if fruit_dict[tree[j]]==0:
                    del fruit_dict[tree[j]]
                j+=1
            if len(fruit_dict)<=2:
                result = max(result,count)
        return result
        '''
        blocks = [(k,len(list(v))) for k,v in itertools.groupby(tree)]
        i,result=0,0
        
        while i<len(blocks):
            j=i
            count=0
            fruit_set = set()
            while j<len(blocks):
                fruit_set.add(blocks[j][0])
                count+=blocks[j][1]
                if len(fruit_set)>2:
                    i=j-1
                    break
                result=max(result,count)
                j+=1
            else:
                break
            
        return result
        '''

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        '''
        fruit_dict = collections.defaultdict(int)
        j,result,count=0,0,0
        for i,t in enumerate(tree):
            fruit_dict[t]+=1
            count+=1
            while len(fruit_dict)>2 and j<len(tree):
                fruit_dict[tree[j]]-=1
                count-=1
                if fruit_dict[tree[j]]==0:
                    del fruit_dict[tree[j]]
                j+=1
            if len(fruit_dict)==2:
                result = max(result,count)
        return result
        '''
        blocks = [(k,len(list(v))) for k,v in itertools.groupby(tree)]
        i,result=0,0
        
        while i<len(blocks):
            j=i
            count=0
            fruit_set = set()
            while j<len(blocks):
                fruit_set.add(blocks[j][0])
                count+=blocks[j][1]
                if len(fruit_set)>2:
                    i=j-1
                    break
                result=max(result,count)
                j+=1
            else:
                break
            
        return result


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        count = collections.Counter()
        
        j = res = 0
        
        for i in range(len(tree)):
            count[tree[i]] += 1
            
            while len(count) > 2:
                count[tree[j]] -= 1
                if count[tree[j]] == 0:
                    del count[tree[j]]
                j += 1
            
            res = max(res, sum(count.values()))
        return res
            
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        res=[]
        ind=0
        if len(tree)==1:
            return 1
        if len(set(tree))<=2:
            return len(tree)
        while ind<len(tree)-1:
            count=0
            types=set()
            for i in range(ind,len(tree)):
                types.add(tree[i])
                if len(types)>2:
                    break
                count+=1
            res.append(count)
            ind+=1
        return max(res)

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
#         winstart=0
#         maxlen=0
#         for winend in range(len(tree)+1):
#             while(len(set(tree[winstart:winend])))>=3:
#                 winstart+=1
#             maxlen=max(maxlen,winend - winstart)
            
#         return maxlen
                
        ans = i = 0
        count = collections.Counter()
        for j, x in enumerate(tree):
            count[x] += 1
            while len(count) >= 3:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        grp = []
        x, y = tree[0], 1
        for e in tree[1:]:
            if e==x:
                y+=1
            else:
                grp.append((x,y))
                x, y = e, 1
        grp.append((x,y))
        
        ret = 0
        pair, pair_sum = [], 0
        for i in range(len(grp)):
            x, y = grp[i]
            if x in pair:
                pair_sum += y
            else:
                if len(pair)<2:
                    pair = pair + [x]
                    pair_sum += y
                else:
                    pair = [grp[i-1][0]] + [x]
                    pair_sum = grp[i-1][1] + y
            # print(pair)
            # print(pair_sum)
            # print('***')
            ret = max(ret, pair_sum)
        return ret
            
            


from collections import defaultdict

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        # freq = defaultdict(int)
        # freq[2] += 1
        # ftypes = set()
        # ftypes.add(2)
        
        if not tree:
            return 0
        
        freq, ftypes, ans, i = defaultdict(int), set(), float('-inf'), 0
        
        for j, num in enumerate(tree):
            freq[num] += 1
            ftypes.add(num)
            
            while len(ftypes) > 2:
                freq[tree[i]] -= 1
                if freq[tree[i]] == 0:
                    ftypes.remove(tree[i])
                i += 1
            
            ans = max(ans, j - i + 1)
            j += 1
            
        return ans

import collections
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        res=i=0
        count=Counter()
        for j, k in enumerate(tree):
            count[tree[j]] +=1
            while len(count)>=3:
                count[tree[i]] -= 1
                if count[tree[i]]==0:
                    del count[tree[i]]
                i +=1
            res=max(res, j-i+1)
        return res

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        i, j = 0, 0
        
        max_fruit = 0
        baskets = defaultdict(int)
        while j <= len(tree) and i < len(tree):
            #print(i, j, baskets)
            if j < len(tree) and len(set(list(baskets.keys()) + [tree[j]])) <= 2:
                baskets[tree[j]] += 1
                j += 1
            else:
                baskets[tree[i]] -= 1
                if baskets[tree[i]] == 0:
                    baskets.pop(tree[i])
                i += 1
            max_fruit = max(sum(baskets.values()), max_fruit)
        return max_fruit


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        i = 0
        maxCol = 0
        baskets = [0,0]
        while i < len(tree) and maxCol + i < len(tree):

            baskets[0] = tree[i]
            j = i +1
            basket1Empty = True
            while j< len(tree):
                if tree[j] != baskets[0] and basket1Empty:
                    baskets[1] = tree[j]
                    basket1Empty = False

                elif tree[j] != baskets[0] and tree[j] != baskets[1]:
                    col = j-i
                    if col > maxCol:
                        maxCol = col
                    break


                j +=1
            col = j-i
            if col > maxCol:
                maxCol = col


            i += 1

        return maxCol


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if len(tree) == 0:
            return 0
        types = {}
        numFruits = 0
        maxNumFruits = 0
        left = 0
        right = 0
        while(right < len(tree)):
            if tree[right] in types:
                types[tree[right]] += 1
            else:
                types[tree[right]] = 1
            numFruits += 1
            right += 1
            
            while len(types) > 2:
                if types[tree[left]] == 1:
                    del(types[tree[left]])
                else:
                    types[tree[left]] -= 1
                left += 1
                numFruits -= 1
            maxNumFruits = max(maxNumFruits, numFruits)
            
            
        return maxNumFruits
                    
                
            

            
                
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if len(tree)<=2: return len(tree)
        
        n = len(tree)
        res,l = 0,0
        while l<n:
            type1, type2 = -1, -1
            next_l = -1 # this denote where we should place l in next subarray
            for r in range(l,n):
                if type1==-1:
                    type1 = tree[r]
                elif tree[r]!=type1 and type2==-1:
                    next_l = r
                    type2 = tree[r]
                elif tree[r] != type1 and tree[r] != type2:
                    break
                r += 1
            res = max(res, r-l)
            if r==n: break
            l = next_l
        return res
                            
            
        
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        hMap = {}
        if not tree:
            return 0
            
        maxCount = 0
        count = 0
        for i in range(len(tree)):
            hMap[tree[i]] = i
            
            if len(hMap) <= 2:
                count += 1
                maxCount = max(count, maxCount)
            else:
                j = sys.maxsize
                r = None
                for k in hMap:
                    if hMap[k] < j:
                        r = k
                        j = hMap[k]
                hMap.pop(r, None)
                count = i - j
                
            # print(tree[i], hMap, count, maxCount)
                
        return maxCount

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        ans = i = 0
        count = collections.Counter()
        for j, x in enumerate(tree):
            count[x] += 1
            while len(count) >= 3:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        counter = {}
        start = 0
        maxL = 0
        for end in range(len(tree)):
            if tree[end] in counter:
                counter[tree[end]] += 1
            else:
                counter[tree[end]] = 1
            while (len(counter) > 2):
                counter[tree[start]] -= 1
                if counter[tree[start]] == 0:
                    del counter[tree[start]]
                start += 1
            maxL = max(maxL, end - start + 1)
        
        return maxL

class Solution:
    def totalFruit(self, f: List[int]) -> int:
        start, count, maxFruits = 0,0,0 
        fruitHash = defaultdict(int)

        for end in range(len(f)):
            if fruitHash[f[end]] == 0:
                count += 1
            fruitHash[f[end]] += 1

            if count <= 2:
                maxFruits = max(maxFruits, end-start+1)

            while count > 2:
                fruitHash[f[start]] -= 1
                start += 1
                if fruitHash[f[start-1]] == 0:
                    count -= 1
                    maxFruits = max(maxFruits, end-start+1)
        return maxFruits

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        max_len = 0
        start = end = 0
        N = len(tree)
        count = 0
        uniq = {}
        
        while end < N:
            cur = tree[end]
            if cur not in uniq:
                uniq[cur] = 0
            
            uniq[cur] += 1
            if uniq[cur] == 1:
                count += 1
            
            while count > 2:
                rem = tree[start]
                uniq[rem] -= 1
                if uniq[rem] == 0:
                    count -= 1
                start += 1
            
            max_len = max(max_len, end - start + 1)
            end += 1
            
        return max_len


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        k = 2
        
        start = 0
        
        freqHashmap = {}
        
        maxFruit = 0
        
        for end in range(len(tree)):
            freqHashmap[tree[end]] = freqHashmap.get(tree[end], 0) + 1
            
            while len(freqHashmap) > k:
                freqHashmap[tree[start]] -= 1
                
                if freqHashmap[tree[start]] == 0:
                    del freqHashmap[tree[start]]
                
                start += 1
            
            maxFruit = max(maxFruit, end - start + 1)
        
        return maxFruit

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        # 包含两个元素的（因为题目说是两个篮子）的最长子序列，采苹果不能后退也不能跳过，所以就是连续子串,采的苹果个数就指的是子串长度
        # 跟之前的题目一模一样
        
        k = 2
        n = len(tree)
        if n < k:
            return n
        
        i = 0
        lookup = {}
        ans = 0
        # 1）有时候会晕是找到字典中的最小下标，还是找到字典中的重复下标
        # 2）因为这里并不是因为出现重复的key而需要移动左指针，而是因为字典里元素太多了而要移动左指针
        # 3）要找到重复了的key，那么就需要在插入之前去判断, 遇到重复的键值i = max(i, 1+lookUp[nums[j]])
        # 4）字典长度超标，不怕重复，因为重复的录入同一个键值一直记录的该key最后一次出现的位置，
        #    4.1）i_min = min(lookup.values()), 另 i= i_min+1, 之所以要一个中间变量i_min，是因为后面要用它去删除键值
        #    4.2）同时删除这个key，否则你每次取min都会找到这个数懂吗
        for j in range(n):
            lookup[tree[j]] = j
            if len(lookup) <= k:
                ans = max(ans, j-i+1)
            else:
                i_min = min(lookup.values())
                del lookup[tree[i_min]]
                i = i_min + 1
                
        return ans
                
            
            


class Solution:
    def totalFruit(self, tree):
        res = cur = count_b = a = b = 0
        for c in tree:
            cur = cur + 1 if c in (a, b) else count_b + 1
            count_b = count_b + 1 if c == b else 1
            if b != c: a, b = b, c
            res = max(res, cur)
        return res

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        # 包含两个元素的（因为题目说是两个篮子）的最长子序列，采苹果不能后退也不能跳过，所以就是连续子串,采的苹果个数就指的是子串长度
        # 跟之前的题目一模一样
        
        k = 2
        n = len(tree)
        if n < k:
            return n
        
        i = 0
        lookup = {}
        ans = 0
        # 1）有时候会晕是找到字典中的最小下标，还是找到字典中的重复下标
        # 2）因为这里并不是因为出现重复的key而需要移动左指针，而是因为字典里元素太多了而要移动左指针
        # 3）要找到重复了的key，那么就需要在插入之前去判断, 遇到重复的键值i = max(i, 1+lookUp[nums[j]])
        # 4）字典长度超标，不怕重复，因为重复的录入同一个键值一直记录的该key最后一次出现的位置，
        #    4.1）i_min = min(lookup.values()), 另 i= i_min+1, 之所以要一个中间变量i_min，是因为后面要用它去删除键值
        #    4.2）同时删除这个key，否则你每次取min都会找到这个数懂吗
        for j in range(n):
            lookup[tree[j]] = j
            if len(lookup) > k:
                i_min = min(lookup.values())
                del lookup[tree[i_min]]
                i = i_min + 1
            ans = max(ans, j-i+1)
                
        return ans
                
            
            


class Solution:
    def totalFruit(self, tree) -> int:
        if len(tree) < 3:
            return len(tree)
        seq_len = [[tree[0], 0]]
        for f in tree:
            if seq_len[-1][0] == f:
                seq_len[-1][1] += 1
            else:
                seq_len.append([f, 1])
        most = seq_len[0][1]
        if len(seq_len) > 1:
            curr_two_types = set([seq_len[0][0], seq_len[1][0]])
            most = curr_most = seq_len[0][1] + seq_len[1][1]
            for i in range(2, len(seq_len)):
                if seq_len[i][0] in curr_two_types:
                    curr_most += seq_len[i][1]
                else:
                    curr_most = seq_len[i][1] + seq_len[i-1][1]
                    curr_two_types = set([seq_len[i][0], seq_len[i-1][0]])
                most = max(most, curr_most)
        return most

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        '''
        Sliding window: the window can at most only have two distinct numbers
        Find the longest sliding window
        Technique: keep the last seen index of each fruit type in my current sliding window
        seen: { x: i, y: j }
        Whenever a new type of fruit is ahead, fast forward the left boundary to min(i,j) + 1
        '''
        ans = 0
        lo, hi = -1, 0
        seen = {}
        for hi in range(len(tree)):
            if tree[hi] not in seen and len(seen) == 2:
                # tree[hi] is not in seen and seen already has 2 elements
                remove = (float('inf'), None)
                for typ in seen:
                    remove = min(remove, (seen[typ], typ))
                lo = seen.pop(remove[1])
            seen[tree[hi]] = hi
            #print(lo, hi, seen)
            ans = max(ans, hi-lo)
        return ans


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        count, i = {}, 0
        for j, v in enumerate(tree):
            count[v] = count.get(v, 0) + 1
            if len(count) > 2:
                count[tree[i]] -= 1
                if count[tree[i]] == 0: del count[tree[i]]
                i += 1
        return j - i + 1


class Solution:
    
    
    def totalFruit(self, tree: List[int]) -> int:
        
        max_count = pair_count = last_count = 0
        fruit_1 = fruit_2 = last_fruit = None
        
        for fruit_type in tree:
            if fruit_type == fruit_1:
                pair_count += 1
                if fruit_type == last_fruit:
                    last_count += 1
                else:
                    last_fruit = fruit_type
                    last_count = 1
            elif fruit_type == fruit_2:
                pair_count += 1
                if fruit_type == last_fruit:
                    last_count += 1
                else:
                    last_fruit = fruit_type
                    last_count = 1
            elif fruit_1 == None:
                fruit_1 = last_fruit = fruit_type
                last_count = 1
                pair_count += 1
            elif fruit_2 == None:
                fruit_2 = last_fruit = fruit_type
                last_count = 1
                pair_count += 1
            else:
                fruit_1 = last_fruit
                fruit_2 = last_fruit = fruit_type
                max_count = max(max_count, pair_count)
                pair_count = last_count+1
                last_count = 1
        
        return max(max_count, pair_count)

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        ans=0
        past=[]
        last=[]
        for i in range(len(tree)):
            #print(past,last)
            if len(past)==0:
                past.append(tree[i])
                last.append(i)
                ans=max((i-last[0]+1),ans)
                continue
            if len(past)==1:
                if tree[i] not in past:
                    past.append(tree[i])
                    last.append(i)
                ans=max((i-last[0]+1),ans)
                continue
            if tree[i] not in past:
                bt=i-1
                ele=tree[bt]
                while tree[bt]==ele:
                    bt-=1
                bt+=1
                past=[tree[bt],tree[i]]
                last=[bt,i]
            ans=max((i-last[0]+1),ans)
        return ans


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        n = len(tree)
        
        if n < 3:
            return n
        
        max_count = 0

        set_1 = {tree[0]}
        count_1 = 1
        set_2 = set_1.copy()
        count_2 = 1
        
        
        for i in range(1, n):
            if tree[i] in set_2:
                count_2 += 1
            else:
                temp = set_1.copy()
                temp.add(tree[i])
                set_2 = temp
                count_2 = count_1 + 1
            if tree[i] in set_1:
                count_1 += 1
            else:
                set_1 = {tree[i]}
                count_1 = 1
                
            max_count = max(max_count, max(count_1, count_2))
            
            
        return max_count
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        l = 0
        count = {}
        
        for r, value in enumerate(tree):
            count[value] = count.get(value,0)+1
            if len(count) > 2:
                count[tree[l]] -= 1
                if count[tree[l]] == 0:
                    del count[tree[l]]
                l += 1
                
        return r-l+1

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        res, start, distince_count, visited = 0, 0, 0, [0] * len(tree)
        for i, c in enumerate(tree):
            if visited[c] == 0:
                distince_count += 1
            visited[c] += 1

            while distince_count > 2:
                visited[tree[start]] -= 1
                if visited[tree[start]] == 0:
                    distince_count -= 1

                start += 1

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

        return res



class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        res = cur = count_b = a = b = 0
        for c in tree:
            cur = cur + 1 if c in (a, b) else count_b + 1
            count_b = count_b + 1 if c == b else 1
            if b != c: a, b = b, c
            res = max(res, cur)
        return res

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        '''
        行不通的 example4就不满足
        #最长的bi-value subarray
        #记录到i处一共几种数出现，两个减出来=2意味着中间只有两种。subarray标准套路.
        from collections import Counter
        n = len(tree)
        record = []
        
        for i in range(n):
            a = len(Counter(tree[:i+1]))
            record.append(a)
        print(record)
        dic = {}
        ans = 0
        dic[0] = [-1,-1] #记录第一次出现和最后一次出现的位置
        for i in range(n):
            if record[i] not in dic.keys():
                dic[record[i]] = [i,i]
            else:
                dic[record[i]][1] = i
            
            if record[i]-2 in dic.keys():
                print(i,dic[record[i]],dic[record[i]-2])
                ans = max(ans,dic[record[i]][1]-dic[record[i]-2][1])
                print('ans=',ans)
            
        
        return ans
        '''
        #sliding  window, two pointers:x,i
        n = len(tree)
        dic = {}
        x = 0
        for i in range(n):
            if tree[i] not in dic.keys():
                dic[tree[i]] = 1
            else:
                dic[tree[i]] += 1
            
            if len(dic) > 2:
                dic[tree[x]] -= 1
                if dic[tree[x]]==0 :
                    del dic[tree[x]]
                x +=1
        return i-x+1

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        deq = []
        currentTwo = set()
        result = 0
        temp = 0
        for e in tree:
            if len(deq) == 0:
                currentTwo.add(e)
                deq.append((e, 1))
                temp = 1
            elif e in currentTwo:
                if e == deq[-1][0]:
                    deq[-1] = (e, deq[-1][1]+1)
                    temp += 1
                else:
                    deq.append((e,1))
                    temp += 1
            else:
                previousOne = deq[-1][0]
                currentTwo = set([previousOne, e])
                deq = deq[-1:]
                temp = deq[-1][1]
                deq.append((e, 1))
                temp += 1

            result = max(result, temp)

        return result
        


class Solution:
    def totalFruit(self, tree) -> int:
        if len(tree) < 3:
            return len(tree)

        # i = 0
        # while i < len(tree) and tree[i] == tree[0]:
        #     i += 1
        # if i == len(tree):
        #     return i
        # most_fruit = i + 1
        # first_type, f_counter = tree[0], i
        # second_type, s_counter = tree[i], 1

        seq_len = [[tree[0], 0]]
        for f in tree:
            if seq_len[-1][0] == f:
                seq_len[-1][1] += 1
            else:
                seq_len.append([f, 1])
        most = curr_most = seq_len[0][1]
        # print(seq_len)
        if len(seq_len) > 1:
            curr_two_types = set([seq_len[0][0], seq_len[1][0]])
            most = curr_most = seq_len[0][1] + seq_len[1][1]
            for i in range(2, len(seq_len)):
                if seq_len[i][0] in curr_two_types:
                    curr_most += seq_len[i][1]
                else:
                    curr_most = seq_len[i][1] + seq_len[i-1][1]
                    curr_two_types = set([seq_len[i][0], seq_len[i-1][0]])
                most = max(most, curr_most)
                # print(\"---\", most)
        return most

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        letter_count = collections.defaultdict(int)
        left, right = 0, 0

        while right < len(tree):
            letter_count[tree[right]] += 1
            right += 1

            if len(letter_count) > 2:
                letter_count[tree[left]] -= 1
                if letter_count[tree[left]] == 0:
                    del letter_count[tree[left]]
                left += 1

        return right - left


class Solution:
    def totalFruit(self, tree):
        ans = cur = one = two = count_one = count_two = 0
        for i in tree:
            if i not in (one, two):
                cur = count_two + 1
            else:
                cur += 1
            if i != two:
                one, two = two, i
                count_two = 1
            else:
                count_two += 1
            ans = max(ans, cur)
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if not len(tree):
            return 0
        count_max = 0
        start = 0
        f_num = tree[0]
        tracking = set()
        tracking.add(f_num)
        last_change = 0
        current_num = tree[0]
        for i in range(1, len(tree)):
            if tree[i] not in tracking:
                if len(tracking) >= 2:
                    count_max = max(i-start, count_max)
                    tracking.remove(f_num)
                    tracking.add(tree[i])
                    f_num = current_num
                    start = last_change
                    
                else:
                    tracking.add(tree[i])
            if tree[i] != current_num:
                last_change = i
                f_num = current_num
                current_num = tree[i]
        count_max = max(len(tree)-start, count_max)
        return count_max

                
                


class Solution:
    # def totalFruit(self, tree):
    #     # scan the array
    #     fruit_block = []
    #     #fruit_block entity = [left_most index in fruit, weight]
    #     for i in range(len(tree)):
    #         if i == 0 or tree[i] != tree[i-1]:
    #             fruit_block.append([i, 1 ])
    #         elif tree[i] == tree[i-1]:
    #             fruit_block[-1][1] += 1
    #     # print(fruit_block)
    #     max_fruit = 0
    #     i = 0
    #     while i < len(fruit_block):
    #         old_i = i
    #         type_fruit = []
    #         weight = 0
    #         for j in range(i, len(fruit_block)):
    #             if tree[fruit_block[j][0]] not in type_fruit:
    #                 type_fruit.append(tree[fruit_block[j][0]])
    #             weight += fruit_block[j][1]
    #             # print(\"type fruit \", type_fruit)
    #             # print(\"weight \", weight)
    #             if len(type_fruit) > 2:
    #                 # print(\"break\")
    #                 i = j -1
    #                 break
    #             max_fruit = max(max_fruit, weight)
    #             if j == len(fruit_block):
    #                 break
    #         if i == old_i:
    #             break
    #     return max_fruit
            
        
#     def totalFruit(self, tree: List[int]) -> int:
        
#         greattest_count = 0
#         for i in range(len(tree)):
#             if i > 0 and tree[i] == tree[i-1]:
#                 print(i)
#                 continue
#             if i > 2 and tree[i] == tree[i-2] and tree[i-1] == tree[i-3] and tree[i] != tree[i-1] and self.checkRepeat(tree, i):
#                 #add function to define tree[i-1] == the newest tree after ones that look like tree[i]
#                 print(i)
#                 continue
#             fruit = self.pickFruit(i, tree)
#             if fruit > greattest_count:
#                 greattest_count = fruit
#         return greattest_count
                
#             # print(count)
#             # print(greattest_count)
        
#         return greattest_count
    
#     def checkRepeat(self,tree, i):
#         for j in range(i, len(tree)):
#             if tree[j] != tree[i]:
#                 return tree[j]==tree[i-1]
#         return True
                
    
#     def pickFruit(self, i, tree):
#         count = 0
#         basket=[\"\", \"\"]
#         for j in range(i, len(tree)):
#             if basket[0] == \"\":
#                 basket[0] = tree[j]
#                 # print(\"basket1: \", basket[0])
#                 count += 1
#                 # print(\"basket1\")
#             elif tree[j] == basket[0]:
#                 count+=1
#                 # print(\"already in basket1\")
#             elif basket[1] == \"\":
#                 basket[1] = tree[j]
#                 count += 1
#                 # print(\"basket2: \", basket[1])
#             elif tree[j] == basket[1]:
#                 count += 1
#                 # print(\"already in basket2\")
#             elif tree[j] not in basket:
#                 return count
#             if j == len(tree)-1:
#                 return count

    def totalFruit(self, tree: List[int]) -> int:
        basket1 = -1
        basket2 = -1
        max_fruit = 0
        start = 0
        end = 0
        i = 0
        while i < len(tree):
            if tree[i] == basket1 or tree[i] == basket2:
                if tree[i] != tree[i-1]:
                    end = i
                i += 1
                continue
            if basket1 == -1:
                basket1 = tree[i]
                end = i
                i += 1
                continue
            if basket2 == -1:
                basket2 = tree[i]
                end = i
                i += 1
                continue
            print(i)
            print(end)
            weight = i - start 
            max_fruit = max(max_fruit, weight)
            #max_fruit = 2 - 0 = 2
            i = end # 1
            start = end # 1
            basket1 = -1
            basket2 = -1
        # if start == 0:
        #     weight = len(tree)
        # else:
        #     weight = len(tree) - start - 1
        weight = len(tree) - start
            
        
        max_fruit = max(max_fruit, weight)
            
        return max_fruit

class Solution:
    def totalFruit(self, t: List[int]) -> int:
        st,a,b,a_hi,res,b_hi = 0,t[0],-1,0,0,0
        for i,v in enumerate(t):
            if v != a and b == -1:
                b = v
                b_hi = i
            elif v == a:
                a_hi = i
            elif v == b:
                b_hi = i
            elif v not in (a,b):
                res = max(res,i-st)
                st_m = min(a_hi,b_hi)
                a,b,st,a_hi,b_hi = t[st_m+1],v,st_m+1,max(a_hi,b_hi),i
        return max(res,len(t)-st)



class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        dic = {}
        i = 0
        j = 0
        MAX = 1
        
        if tree == None or len(tree) == 0:
            return None
        
        while j < len(tree):
            if len(dic) <= 2:
                dic[tree[j]] = j
                j+=1
            if len(dic) > 2:
                mins = len(tree) -1
                
                for val in list(dic.values()):
                    mins = min(mins,val)
                
                i = mins + 1
                del dic[tree[mins]]
            
            MAX = max(MAX,j-i)
        return MAX
            
                              
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if not tree:
            return 0
        l = 0
        mp = collections.defaultdict(int)
        fruits = 1
        for i in range(0, len(tree)):
            mp[tree[i]] += 1
            while len(mp) > 2:
                mp[tree[l]] -= 1
                if mp[tree[l]] == 0:
                    del mp[tree[l]]
                l += 1
            fruits = max(fruits, i-l+1)
        return fruits
            
                
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        left = 0
        right = 0
        window = set()
        res = 0
        last_index = collections.defaultdict(int)
        
        for right in range(len(tree)):
            fruit_type = tree[right]
            last_index[fruit_type] = right
            if tree[right] in window or len(window) < 2:
                window.add(tree[right])
            else:
                window.add(tree[right])
                while len(window) > 2:
                    fruit_type = tree[left]
                    if left == last_index[fruit_type]:
                        window.remove(fruit_type)
                    left += 1
            res = max(res, right - left + 1)
        return res


# longest run that only contains two symbols?
# 6:52 -> 7:01 TLE on naive n^2 solution
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        counts = 0
        starts = {}
        start = end = 0
        longest = 0
        
        def find_earliest(starts):
            earliest = len(tree)
            for key in starts:
                earliest = min(starts[key], earliest)
            return earliest
        
        while end < len(tree):
            # print(start, end, starts)
            current = tree[end]
            if current in starts:
                starts[current] = end
                end += 1
            else:
                if counts == 2:
                    earliest = find_earliest(starts)
                    del starts[tree[earliest]]
                    start = earliest + 1
                    counts -= 1
                else:
                    starts[current] = end
                    counts += 1
                    end += 1
            longest = max(end - start, longest)
        
        return max(end - start, longest)
        
        
#         longest = 0
        
#         def contains_two_symbols(subarray):
#             c = Counter(subarray)
#             contains = 0
#             for key in c:
#                 if c[key]:
#                     contains += 1
#             return contains < 3
            
#         for i in range(len(tree)):
#             for j in range(i + 1, len(tree) + 1):
#                 if contains_two_symbols(tree[i:j]):
#                     longest = max(longest, j - i)
        
#         return longest


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        ans = i = 0
        count = collections.defaultdict(int)
        for j, ftype in enumerate(tree):
            count[ftype] += 1
            while len(count) > 2:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    count.pop(tree[i])
                i += 1
            ans = max(ans, j - i + 1)
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        # length of the longest subarray containing at most 2 distinct elements
        if len(tree) == 0: return 0
        i, j, n_kind, res = 0, 0, 1, 1
        cnts = [0,] * len(tree)
        cnts[tree[0]] += 1
        while True:
            while n_kind <= 2:
                res = max(res, j-i+1)
                j += 1
                if j >= len(tree): 
                    return res  # ?
                if cnts[tree[j]] == 0:
                    n_kind += 1
                cnts[tree[j]] += 1
            while n_kind > 2:
                cnts[tree[i]] -= 1
                if cnts[tree[i]] == 0:
                    n_kind -= 1
                i += 1
        return res


from collections import deque
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        maxFruits = 0
        fruitTypes = set()        
        queue = deque()
        
        for i in tree:
            if i in fruitTypes or len(fruitTypes) < 2:
                fruitTypes.add(i)
            else:
                prevFruit = queue[-1]
                j = len(queue)-2
                while j >= 0 and queue[j] == prevFruit:
                    j -= 1
                while j >=0:
                    queue.popleft()
                    j -= 1
                for k in list(fruitTypes):
                    if k == prevFruit:
                        continue
                    else:
                        fruitTypes.remove(k)
                fruitTypes.add(i)
            queue.append(i)
            maxFruits = max(len(queue), maxFruits)
        return maxFruits
            
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        l, res, check = 0, 0, dict()
        for i, t in enumerate(tree):
            check[t] = check.get(t, 0) + 1
            if len(check) <= 2:
                res = max(res, i - l + 1)
            while len(check) > 2:
                check[tree[l]] -= 1
                if check[tree[l]] == 0:
                    del check[tree[l]]
                l += 1
        return res

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if len(tree) <= 2:
            return len(tree)
        collection_list = [tree[0]]
        counter = 1
        _max = 1
        rep = 1
        for i in range(1, len(tree)):
            if tree[i] in collection_list:
                if tree[i] == tree[i-1]:
                    rep += 1
                else:
                    rep = 1
                counter += 1
                if counter > _max:
                    _max = counter
            else:
                if len(collection_list) == 1:
                    collection_list.append(tree[i])
                    counter += 1
                    rep = 1
                    if counter > _max:
                        _max = counter
                else:
                    collection_list = [tree[i-1], tree[i]]
                    counter = 1 + rep
                    rep = 1
        return _max

from collections import Counter
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        d = collections.defaultdict(int)
        left = 0 
        total = 0
        for idx, i in enumerate(tree):
            d[i] += 1 
            while(len(d) > 2):
                d[tree[left]] -= 1 
                if(d[tree[left]] == 0):
                    del d[tree[left]]
                left += 1 
                
            total = max(total, idx - left + 1)
        return total


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if len(tree) == 0 or len(tree) == 1:
            return len(tree);
        A = [-1]*2
        B = [-1]*2
        f1 = -1
        f2 = -1
        n = len(tree)
        maxi = 1
        i=0
        while i<n:
            if tree[i]==f1 or tree[i]==f2:
                if tree[i]==f1:
                    A[1]=i
                else: 
                    B[1]=i
            else:
                if tree[i-1]==f1:
                    f2=tree[i]
                    A[0]=B[1]+1
                    B[0]=B[1]=i
                else:
                    f1=tree[i]
                    B[0]=A[1]+1
                    A[0]=A[1]=i
                
            maxi = max(maxi,max(A[1],B[1])-min(A[0],B[0]))
            i = i+1
        return maxi+1
            



class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        idx, baskets, res = -1, collections.deque(maxlen=2), 0
        for i, x in enumerate(tree):
            if x not in [y[0] for y in baskets]:
                if len(baskets) == 2:
                    res, idx = max(res, i - idx - 1), baskets[0][1]
                baskets.append([x, i])
            else:
                if x == baskets[0][0]:
                    baskets.popleft()
                    baskets.append([x, i])
                else:
                    baskets[1][1] = i
                
        return max(res, len(tree) - 1 - idx)

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        store = collections.defaultdict(lambda:0)
        ans = 0
        i=0
        for k,val in enumerate(tree):
            store[val]+=1
            while len(store)>2:
                store[tree[i]]-=1
                if store[tree[i]]==0:
                    del store[tree[i]]
                i+=1
            ans = max(ans,k-i+1)
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        f1, f2= [-1,-1],[-1,-1]
        res, fruit1, fruit2 = 0, -1, -1
        for i in range(len(tree)):
            if tree[i] not in [fruit1,fruit2]:   
                if f2[1]>f1[1]:
                    f2[0] = f1[1]+1
                    f1 = [i,i]
                    fruit1 = tree[i]
                else:
                    f1[0] = f2[1]+1
                    f2 = [i,i]
                    fruit2 = tree[i]
            elif tree[i] == fruit1: f1[1] = i
            else: f2[1] = i
            res = max(res,max(f1[1],f2[1]) - min(f1[0],f2[0]))
        return res+1

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        # compress the tree
        compressedTree = []
        
        current = [tree[0], 0]
        for index in range(len(tree)):
            fruit = tree[index]
            if fruit != current[0]:
                compressedTree.append(current)
                current = [fruit, 1]
            else:
                current[1] += 1
        compressedTree.append(current)
        
        ans = i = 0
        while i < len(compressedTree):
            # We'll start our scan at block[i].
            # types : the different values of tree[i] seen
            # weight : the total number of trees represented
            #          by blocks under consideration
            types, weight = set(), 0

            # For each block from i and going forward,
            for j in range(i, len(compressedTree)):
                # Add each block to consideration
                types.add(compressedTree[j][0])
                weight += compressedTree[j][1]

                # If we have 3 types, this is not a legal subarray
                if len(types) >= 3:
                    i = j-1
                    break

                ans = max(ans, weight)

            # If we go to the last block, then stop
            else:
                break

        return ans

from collections import defaultdict

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        l, r = 0, 0
        d = defaultdict(int)
        res = 0
        
        
        for r in range(len(tree)):
            d[tree[r]] += 1
            while len(d) > 2:
                #print(l)
                d[tree[l]] -= 1
                if d[tree[l]] == 0:
                    d.pop(tree[l])
                l += 1
            res = max(res, r - l + 1)
            #print(r,l)
        
        return res
        
#         while r < len(tree):
            
#             while len(d) <= 2:
#                 r += 1
#                 if r < len(tree):
#                     d[tree[r]] += 1
#                 else:
#                     break
                
#             if len(d) > 2 or r == len(tree):
#                 res = max(res, r - l)
                
# #            print(\"1s\", r, l)
            
#             while len(d) > 2:
#                 d[tree[l]] -= 1
#                 if d[tree[l]] == 0:
#                     d.pop(tree[l])
#                 l += 1
                
# #            print(\"2s\", r, l)
#         return res
            
        


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        '''
            [0,1,2,2]
            ^
            
            [3,3,3,1,2,1,1,2,3,3,4]
        
        
        '''
        n = len(tree)
        res = 0
        
        window = defaultdict(int)
        count = 0
        left =  0
        
        for idx in range(n):
            curr = tree[idx]
            if window[curr] == 0:
                count += 1
            window[curr] += 1
            if count <= 2:
                res = max(res, idx - left + 1)
            while count > 2:
                window[tree[left]] -= 1
                if window[tree[left]] == 0:
                    count -= 1
                left += 1
        return res
    
                
            
            
                


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        left = 0
        right = 0
        window = set()
        res = 0
        last_index = collections.defaultdict(int)
        
        while left < len(tree) and right < len(tree):
            fruit_type = tree[right]
            last_index[fruit_type] = right
            if tree[right] in window or len(window) < 2:
                window.add(tree[right])
            else:
                window.add(tree[right])
                while len(window) > 2:
                    fruit_type = tree[left]
                    if left == last_index[fruit_type]:
                        window.remove(fruit_type)
                    left += 1
            res = max(res, right - left + 1)
            right += 1
        return res


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        best_so_far = start = 0
        fruit_1 = fruit_2 = fruit_1_last_index = fruit_2_last_index = None
        
        for end in range(len(tree)):
            # If we haven't picked any fruit yet, put this fruit in basket 1
            if fruit_1 is None:
                fruit_1 = tree[end]
                fruit_1_last_index = end
                
            # If we haven't picked two different fruits yet, put this fruit in backet 2
            elif fruit_2 is None and tree[end] != fruit_1:
                fruit_2 = tree[end]
                fruit_2_last_index = end
                
            # We have picked at least 2 different fruits so far
            else:
                # If this is basket 1's fruit, remember this as the most recent place we saw fruit 1
                if tree[end] == fruit_1:
                    fruit_1_last_index = end
                    
                # If this is basket 2's fruit, remember this as the most recent place we saw fruit 2
                elif tree[end] == fruit_2:
                    fruit_2_last_index = end
                    
                # This is neither fruit 1 nor fruit 2
                else:
                    # This is as far as we can go with these two fruits. Remember how many fruits we got.
                    best_so_far = max(best_so_far, end - start)
                    
                    # Replace <the fruit whose most recent sighting was longer ago> with this new fruit
                    if fruit_1_last_index < fruit_2_last_index:
                        start = fruit_1_last_index + 1
                        fruit_1 = tree[end]
                        fruit_1_last_index = end
                    else:
                        start = fruit_2_last_index + 1
                        fruit_2 = tree[end]
                        fruit_2_last_index = end
        
        return max(best_so_far, len(tree) - start)

class Solution:
    
    def totalFruit(self, tree: List[int]) -> int:
        
        blocks = [(k, len(list(v))) for k, v in itertools.groupby(tree)]
        
        ans = i = 0
        
        while i < len(blocks):
            
            types, weight = set(), 0
            
            for j in range(i, len(blocks)):
                
                types.add(blocks[j][0])
                
                weight += blocks[j][1]
                
                if len(types) >= 3:
                    
                    i = j - 1
                    
                    break
                    
                ans = max(ans, weight)
                
                
            else:
                
                break
                
        return ans
            
            
        
            
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        count, i, j = {}, 0, 0
        max_cnt = 0
        while j < len(tree):
            v = tree[j]
            count[v] = count.get(v, 0) + 1
            if len(count) <= 2:
                max_cnt = max(sum(count.values()), max_cnt)
            while len(count) > 2:
                count[tree[i]] -= 1
                if count[tree[i]] == 0: del count[tree[i]]
                i += 1
            j += 1
        return max_cnt


import collections
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        left = 0
        right = 0
        fruitsTypes = defaultdict(int)
        numFruits = 0
        maxNumFruit = 0
        while(right < len(tree)):
            fruitsTypes[tree[right]] += 1
            numFruits += 1
            right += 1
            while len(fruitsTypes) > 2:
                fruitsTypes[tree[left]] -= 1
                if fruitsTypes[tree[left]] == 0:
                    del(fruitsTypes[tree[left]])
                numFruits -= 1
                left += 1
            maxNumFruit = max(maxNumFruit, numFruits)
        return maxNumFruit
                
                
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        maxCount = count = 0
        head = back = 0
        buckets = dict()
        while back < len(tree):
            fruit = tree[back]
            if fruit in buckets:
                buckets[fruit] += 1  
            else:
                buckets[fruit] = 1
                while len(list(buckets.keys())) > 2:
                    dropFruit = tree[head]
                    buckets[dropFruit] -= 1
                    if buckets[dropFruit] == 0:
                        buckets.pop(dropFruit)
                    count -= 1
                    head += 1
            count += 1
            maxCount = max(maxCount, count)
            back += 1
        return maxCount
                
                    
                    
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        result = 0
        left, right = 0, 0
        basket = collections.defaultdict(int)
        
        
        while right < len(tree):
            basket[tree[right]] += 1
            
            while len(basket) > 2:
                if basket[tree[left]] == 1:
                    basket.pop(tree[left])
                else:
                    basket[tree[left]] -= 1
                left += 1
            
            result = max(result, right - left + 1)
            right += 1
            
            
        return result

class Solution(object):
    def totalFruit(self, tree):
        blocks = [(k, len(list(v)))
                  for k, v in itertools.groupby(tree)]

        ans = i = 0
        while i < len(blocks):
            # We'll start our scan at block[i].
            # types : the different values of tree[i] seen
            # weight : the total number of trees represented
            #          by blocks under consideration
            types, weight = set(), 0

            # For each block from i and going forward,
            for j in range(i, len(blocks)):
                # Add each block to consideration
                types.add(blocks[j][0])
                weight += blocks[j][1]

                # If we have 3 types, this is not a legal subarray
                if len(types) >= 3:
                    i = j-1
                    break

                ans = max(ans, weight)

            # If we go to the last block, then stop
            else:
                break

        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        blocks = []
        
        i = 0
        while i < len(tree):
            j = i + 1
            length = 1
            while j < len(tree) and tree[j] == tree[j-1]:
                length += 1
                j += 1
                
            blocks.append((tree[i], length))
            i = j
            
        
        maxi = 0

        i = 0
        while i < len(blocks):
            types, cur = set(), 0
            for j in range(i, len(blocks)):
                types.add(blocks[j][0])
                cur += blocks[j][1]
                if len(types) > 2:
                    i = j - 1
                    break
                
            
                maxi = max(maxi, cur)
            else:
                break
        return maxi

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        i, j = 0, 0
        res = 0
        d = {} 
        while j < len(tree):
            d[tree[j]] = d.get(tree[j], 0) + 1
            if len(d) <= 2:
                res = max(res, j - i + 1)
            else: 
                while len(d) > 2:
                    d[tree[i]] = d[tree[i]] - 1
                    if d[tree[i]] == 0:
                        d.pop(tree[i])
                    i += 1
            j += 1
        return res
                
            
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        t1 = t2 = -1
        t1s = -1
        ans = 0;
        for i in range(0, len(tree)):
            t = tree[i]
            if t != t1 and t != t2:
                ans = max(ans, i - t1s)
                t1s = i
                while (t1s > 0 and tree[t1s - 1] == tree[i - 1]):
                    t1s -= 1
                t1 = tree[i - 1]
                t2 = t
        ans = max(ans, len(tree) - t1s)
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        block = []
        prev = tree[0]
        start = 0
        for i in range(1, len(tree)):
            if prev != tree[i]:
                block.append((prev, i-start))
                start = i
                prev = tree[i]
        block.append((prev, len(tree) - start))
        head, tail = 0, 1
        basket = {block[0][0]: block[0][1]}
        res = block[0][1]
        while tail < len(block):
            t, q = block[tail]
            if t in list(basket.keys()):
                basket[t] += q
            else:
                if len(basket) < 2:
                    basket[t] = q
                else:
                    while len(basket) == 2:
                        ht, hq = block[head]
                        head += 1
                        basket[ht] -= hq
                        if basket[ht] == 0:
                            basket.pop(ht)
                    basket[t] = q
            val = 0
            for tt in list(basket.keys()):
                val += basket[tt]
            res = max(res, val)
            tail += 1
        return res


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        count, i, j = {}, 0, 0
        max_cnt = 0
        while j < len(tree):
            # print(count)
            v = tree[j]
            count[v] = count.get(v, 0) + 1
            if len(count) <= 2:
                max_cnt = max(sum(count.values()), max_cnt)
            while len(count) > 2:
                count[tree[i]] -= 1
                if count[tree[i]] == 0: del count[tree[i]]
                i += 1
            j += 1
        return max_cnt
                
        
# j = 2
# i = 1
# count = {
#     3: 2,
#     1: 1,
#     2: 1
# }


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        i = 0
        j = 0
        my_map = {}
        max_len = 0
        while i < len(tree):
            while i < len(tree) and (tree[i] not in my_map and len(my_map) < 2 or tree[i] in my_map):
                if tree[i] not in my_map:
                    my_map[tree[i]] = 0
                my_map[tree[i]] += 1
                i += 1
            max_len = max(max_len, i - j)
            while len(my_map) == 2: 
                my_map[tree[j]] -= 1
                if my_map[tree[j]] == 0:
                    del my_map[tree[j]]
                j += 1
            
        return max_len


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        fruits = {}
        maxNum = 0
        
        left = 0
        right = 0
        while right < len(tree):
            while len(fruits) < 3 and right < len(tree):
                fruit = tree[right]
                if fruit not in fruits:
                    fruits[fruit] = 0
                fruits[fruit] += 1
                if len(fruits) < 3:
                    maxNum = max(maxNum, sum(fruits.values()))
                right += 1
            while len(fruits) > 2 and left < right:
                fruit = tree[left]
                fruits[fruit] -= 1
                if fruits[fruit] == 0:
                    del fruits[fruit]
                left += 1
        return maxNum

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if len(tree) == 1:
            return 1
        lo = 0
        hi = 1
        baskets = set()
        baskets.add(tree[0])
        bmaps = {}
        bmaps[tree[0]] = 1
        cnt = 1
        while hi < len(tree):
            baskets.add(tree[hi])
            if tree[hi] in bmaps:
                bmaps[tree[hi]] += 1
            else:
                bmaps[tree[hi]] = 1

            while len(baskets) > 2:
                if bmaps[tree[lo]] == 1:
                    baskets.remove(tree[lo])
                    bmaps[tree[lo]] = 0
                else:
                    bmaps[tree[lo]] -= 1
                lo += 1
            cnt = max(hi - lo + 1, cnt)
            hi += 1
        return cnt


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        l, nums, res = 0, collections.Counter(), 0
        for r in range(len(tree)):
            nums[tree[r]] += 1
            while len(nums) > 2:
                nums[tree[l]] -= 1 
                if not nums[tree[l]]:
                    nums.pop(tree[l])
                l += 1
            res = max(res, r - l + 1)
        return res        

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if not tree:
            return 0
        i = 0
        max_value = 0
        count = Counter()
        for index, value in enumerate(tree):
            count[value] += 1
            while len(count) >= 3:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i += 1
            max_value = max(max_value, index - i + 1)
        return max_value

class Solution:
    def totalFruit(self, s: List[int]) -> int:
        m=0
        arr={}
        i=0
        k=2
        for j in range(len(s)):
            if s[j] not in arr:
                arr[s[j]]=0
            arr[s[j]]+=1
            while len(arr)>k:
                x=s[i]
                arr[x]-=1
                if arr[x]==0:
                    arr.pop(x)
                i+=1
            m=max(m,j-i+1)
        return m

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        
        
        blocks = []
        i=0
        while i<len(tree):
            start=i
            while i+1<len(tree) and tree[i+1]==tree[start]:
                i+=1
            blocks.append((tree[start],i-start+1))
            i = i+1
            

        ans =0
        i=0
        while i<len(blocks):
            types = set()
            weight = 0
            j=i
            while j<len(blocks):
                types.add(blocks[j][0])
                weight+=blocks[j][1]
                
                if len(types)>2:
                    i=j-1
                    break
                
                ans = max(ans,weight)
                j+=1
                
                if j==len(blocks):
                    i=j
            
            if i==len(blocks):
                break
        
        return ans


from collections import Counter
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        d = Counter()
        left = 0 
        total = 0
        for idx, i in enumerate(tree):
            d[i] += 1 
            while(len(d) > 2):
                d[tree[left]] -= 1 
                if(d[tree[left]] == 0):
                    del d[tree[left]]
                left += 1 
                
            total = max(total, idx - left + 1)
        return total


class Solution:
    def total(self, fruits):
        total = 0
        for key in fruits:
            total += fruits[key]
        
        return total
    
    def totalFruit(self, tree: List[int]) -> int:
        
        fruits = {}
        left_index = 0
        best = 0
        
        for right_index in range(len(tree)):
            curr_fruit = tree[right_index]
            
            if curr_fruit not in fruits:
                fruits[curr_fruit] = 1
            else:
                fruits[curr_fruit] += 1
            
            while len(fruits) > 2:
                old_fruit = tree[left_index]
                fruits[old_fruit] -= 1
                if fruits[old_fruit] == 0:
                    del fruits[old_fruit]
                left_index += 1 
                
            best = max(best, self.total(fruits))
        
        return best
            


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        result = 0
        ptr = 0
        count = collections.Counter()
        for i, t in enumerate(tree):
            count[t] += 1
            while len(count) >= 3:
                count[tree[ptr]] -= 1
                if count[tree[ptr]] == 0:
                    del count[tree[ptr]]
                ptr += 1
            result = max(result, i - ptr + 1)
        return result


class Solution:
    def totalFruit(self, tree: List[int]) -> int:

        max_len = 0
        basket = collections.Counter()
        start = 0
        
        for end, fruit in enumerate(tree):
            basket[fruit] += 1
            
            while len(basket) >= 3:
                basket[tree[start]] -= 1
                
                if basket[tree[start]] == 0:
                    del basket[tree[start]]
                    
                start += 1
            max_len = max(max_len, end - start + 1)
            
        return max_len

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        ans = i = 0
        count = collections.Counter()
        for j, x in enumerate(tree):
            count[x] += 1
            while len(count) >= 3:
                count[tree[i]] -= 1
                if count[tree[i]] == 0:
                    del count[tree[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans
            
            
            
                
            


# 问题可以抽象为给定一个数组，求解最多选择两种数字的情况下，最大的连续子序列长度，其中数组和原题目一样，每一个数字代表一个水果。

# 我们可以使用滑动窗口来解决。 思路和 【1004. 最大连续 1 的个数 III】滑动窗口（Python3） 一样。



class Solution:
    def atMostK(self, nums, K):
        counter = collections.Counter()
        res = i = 0
        for j in range(len(nums)):
            if counter[nums[j]] == 0:
                K -= 1
            counter[nums[j]] += 1  #然后加上1
            while K < 0:
                counter[nums[i]] -= 1  #移去最外面的，然后自己往左走
                if counter[nums[i]] == 0:
                    K += 1  #说明有一个品种多出来了，所以在没有到可以移出品种之前，需要一直变动
                i += 1
            res = max(res, j - i + 1)  #因为还要多一个
        return res

    def totalFruit(self, tree: List[int]) -> int:
        return self.atMostK(tree, 2)   #最多两个

# 复杂度分析

# 时间复杂度：O(N)O(N)
# 空间复杂度：O(N))O(N)) （我们使用了Counter）


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
#dynamic sliding windo        
        maxi=0
        if len(tree)==1:
            return 1
        l=[]
        s=set()
        for i in range(len(tree)):
            l.append(tree[i])
            s.add(tree[i])
            if len(s)>2:#we need to change the start of the window, remove until the size of set reduces to less than=2
                #l=l[::-1]
                while len(set(l))>2:
                    #l.pop()
                    l=l[1:]#pop the first element until the set has less than equal to 2 elements
                #l=l[::-1]
                s=set(l)#new version of set
            maxi=max(maxi,len(l))
        return maxi
#increasing the sizee of sliding window by starting at each element        
#         maxi=0
#         if len(tree)==1:
#             return 1
            
#         for i in range(len(tree)):
#             s=set()
#             s.add(tree[i])
#             for j in range(i+1,len(tree)):
#                 s.add(tree[j])
#                 if len(s)>2:
#                     break
#                 maxi=max(maxi,j-i+1)
#         return maxi
        
        # for i in range(len(tree),0,-1):
        #     start=0
        #     end=i
        #     for j in range(len(tree)-i+1):
        #         s=tree[start:end]
        #         start+=1
        #         end+=1
        #         if len(set(s))<=2:
        #             return i


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
#dynamic sliding windo        
        maxi=0
        if len(tree)==1:
            return 1
        l=[]
        s=set()
        for i in range(len(tree)):
            l.append(tree[i])
            s.add(tree[i])
            if len(s)>2:
                #l=l[::-1]
                while len(set(l))>2:
                    #l.pop()
                    l=l[1:]#pop the first element until the set has less than equal to 2 elements
                #l=l[::-1]
                s=set(l)
            maxi=max(maxi,len(l))
        return maxi
#increasing the sizee of sliding window by starting at each element        
#         maxi=0
#         if len(tree)==1:
#             return 1
            
#         for i in range(len(tree)):
#             s=set()
#             s.add(tree[i])
#             for j in range(i+1,len(tree)):
#                 s.add(tree[j])
#                 if len(s)>2:
#                     break
#                 maxi=max(maxi,j-i+1)
#         return maxi
        
        # for i in range(len(tree),0,-1):
        #     start=0
        #     end=i
        #     for j in range(len(tree)-i+1):
        #         s=tree[start:end]
        #         start+=1
        #         end+=1
        #         if len(set(s))<=2:
        #             return i


class Solution(object):
    def totalFruit(self, tree):
        n = len(tree)
        left, right = 0, 0
        basket = {}
        
        ans = 0
        while right<n:
            while left<right and len(basket)>1:
                basket.update({tree[left]:basket.get(tree[left], 0)-1})
                if basket.get(tree[left], None) == 0:
                    basket.pop(tree[left])
                left +=1
                
            basket.update({tree[right]:basket.get(tree[right], 0)+1})
            right += 1
            while right<n and basket.get(tree[right], 0) > 0:
                basket.update({tree[right]:basket.get(tree[right], 0)+1})
                right += 1
            # print(left, right, basket)
            ans = max(ans, right-left)
        return ans

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        N = len(tree)
        
        cache = Counter()
        
        left = right = 0
        maxx = 0
        while left < N and right < N:
            # while len(cache) < 2 and right < N:
            curr = tree[right]
            cache[curr] += 1                
            # right += 1
                
            while len(cache) > 2 and left < N:
                # print(cache)
                curr = tree[left]
                cache[curr] -= 1
                if cache[curr] <= 0:
                    del cache[curr]
                left += 1
            
            # print(tree[left:right+1])
            maxx = max(maxx, right-left+1)
            right += 1
            
        return maxx

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        l, nums, ans = 0, collections.Counter(), 0
        for r in range(len(tree)):
            nums[tree[r]] += 1
            while len(nums) > 2:
                nums[tree[l]] -= 1
                if not nums[tree[l]]:
                    del nums[tree[l]]
                l += 1
            ans = max(ans, r - l + 1)
        return ans
                    
                    
                


from collections import defaultdict

class Solution:
    def totalFruit(self, tree: List[int]) -> int:

        maxAmountOfFruit = 0
        startIndex, endIndex = 0, 0

        countByFruit = defaultdict(int)
        countByFruit[tree[startIndex]] = 1
        
        while endIndex < len(tree):
            while len(countByFruit) > 2:
                fruitToRemove = tree[startIndex]
                countByFruit[fruitToRemove] -= 1
                if countByFruit[fruitToRemove] == 0:
                    del countByFruit[fruitToRemove]
                startIndex += 1
            maxAmountOfFruit = max(maxAmountOfFruit, endIndex - startIndex + 1)
            endIndex += 1
            if endIndex != len(tree):
                countByFruit[tree[endIndex]] += 1
        return maxAmountOfFruit


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        cnt = collections.Counter()
        i = 0
        res = 0
        for j in range(len(tree)):
            cnt[tree[j]] += 1
            while len(cnt) > 2:
                cnt[tree[i]] -= 1
                if cnt[tree[i]] == 0:
                    cnt.pop(tree[i])
                i += 1
            res = max(res, sum(cnt.values()))
        return res
            
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        # fruit_1, fruit_2 = None, None
        # pos_1, pos_2 = -1, -1
        # i = 0
        # max_len = 0
        # for t in range(len(tree)):
        #     if tree[t]==fruit_1:
        #         fruit_1, fruit_2 = fruit_2, fruit_1
        #         pos_1, pos_2 = pos_2, t
        #     elif tree[t]==fruit_2:
        #         pos_2 = t
        #     else:
        #         fruit_1, fruit_2 = fruit_2, tree[t]
        #         i = pos_1 + 1
        #         pos_1, pos_2 = pos_2, t
        #     if t - i + 1 > max_len:
        #         max_len = t - i + 1
        # return max_len


class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        left, right = 0, 0
        res = 0
        cnt = collections.defaultdict(int)
        while right < len(tree):
            cnt[tree[right]] += 1
            while len(cnt) > 2:
                cnt[tree[left]] -= 1
                if cnt[tree[left]] == 0:
                    del cnt[tree[left]]
                left += 1
            res = max(res, right - left + 1)
            right += 1
        return res