Find Maximum Candies With Two Types
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a row of candies represented by an array `candies`, where `candies[i]` is the type of the candy at position `i`.
You may choose any starting position and then move only to the right, taking every candy you encounter. However, you can carry candies of at most two distinct types. Once you encounter a candy of a third distinct type, you must stop before taking it.
Return the maximum number of candies you can take.
Example:
```text
Input: candies = [1, 2, 1, 2, 3, 2, 2]
Output: 4
Explanation: Starting at index 0, you can take [1, 2, 1, 2]. The next candy has type 3, which would be a third type, so you must stop.
```
Follow-up: Solve it in linear time.
Quick Answer: This question evaluates algorithmic problem-solving with arrays, focusing on managing constraints on the number of distinct element types in a contiguous sequence and maintaining element frequency/state during a traversal.
You are given a row of candies represented by an array `candies`, where `candies[i]` is the type of candy at position `i`.
You may choose any starting position and then move only to the right, taking every candy you encounter. However, you can carry candies of at most two distinct types. As soon as the next candy would introduce a third distinct type, you must stop before taking it.
Return the maximum number of candies you can take.
In other words, find the length of the longest contiguous subarray that contains at most two distinct values.
Follow-up: Solve it in linear time.
Constraints
- 0 <= len(candies) <= 200000
- -1000000000 <= candies[i] <= 1000000000
Examples
Input: [1, 2, 1, 2, 3, 2, 2]
Expected Output: 4
Explanation: The longest valid segment is [1, 2, 1, 2], which has only two types and length 4.
Input: [0, 1, 2, 2]
Expected Output: 3
Explanation: The best segment is [1, 2, 2], which contains only types 1 and 2.
Hints
- Try maintaining a sliding window of consecutive candies that is always valid.
- Use a hash map to count how many candies of each type are currently inside the window, and shrink the left side when more than two types appear.