Fruit Into Baskets

Problem

A row of fruit trees is given as an integer array fruits, where fruits[i] is the type of fruit on tree i. You carry exactly two baskets, and each basket may hold only one type of fruit (any quantity). You pick a starting tree, then move right taking exactly one fruit from every tree you pass, stopping the moment you reach a tree whose fruit fits in neither basket. Return the maximum number of fruits you can collect.

• The row has between 1 and 100,000 trees.
• Fruit types are non-negative integers; there is no bound on how many distinct types appear.

Examples

• fruits = [4, 7, 4, 4] → 4. Only two types appear, so the whole row can be picked.
• fruits = [3, 5, 1, 1, 5] → 4. Starting at the second tree collects [5, 1, 1, 5]; starting at the first would stop at the 1.
• fruits = [6, 6, 2, 8, 2, 2, 8, 8, 1] → 6. [2, 8, 2, 2, 8, 8] uses types 2 and 8; the 6s before it and the 1 after it would each need a third basket.

Hints

1. Restate the story without fruit: what property must the chosen contiguous run have?
2. Once a run needs three baskets, adding more trees to its right cannot fix it. Which end of the run has to move?
3. Sliding window with a count map of types in the window; when a third type appears, advance the left edge until one type's count drops to zero.