Medium

Fruit Into Baskets

LAB

Return the length of the longest contiguous subarray containing at most two distinct values.

EXAMPLES

Example 1

Input
{
  "fruits": [
    1,
    2,
    1
  ]
}

Output
3

FUNCTION SHAPE

fruits: intArray→int

SOLUTION NOTE

This is exactly the same as Q340 with k = 2. Note: fruits is a list of ints, not a string, but you can easily adapt the template.

Reveal reference solution +

pythonREFERENCE

def totalFruit(self, fruits: List[int]) -> int:
    n, l, freq, res = len(fruits), 0, Counter(), 0

    for r in range(n):
        freq[fruits[r]] += 1

        while len(freq) > 2:
            freq[fruits[l]] -= 1
            if freq[fruits[l]] == 0: del freq[fruits[l]]
            l += 1

        res = max(res, r - l + 1)

    return res

# Or simply:
# return lengthOfLongestSubstringKDistinct(fruits, 2)

TimeO(n)

SpaceO(1)

Open on LeetCode ↗