Problem Statement

You are visiting a farm to collect fruits. The farm has a single row of fruit trees. You will be given two baskets, and your goal is to pick as many fruits as possible to be placed in the given baskets.

You will be given an array of characters where each character represents a fruit tree. The farm has following restrictions:

1. Each basket can have only one type of fruit. There is no limit to how many fruit a basket can hold.
2. You can start with any tree, but you can’t skip a tree once you have started.
3. You will pick exactly one fruit from every tree until you cannot, i.e., you will stop when you have to pick from a third fruit type.

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

Example 1:

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

Example 2:

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

Constraints:

• 1 <= arr.length <= 10^5
• 0 <= arr[i] < arr.length

Solution

To solve this problem, we use a sliding window approach. This technique is effective for problems involving contiguous subarrays or sublists. The sliding window approach allows us to maintain a window of elements that meet a certain condition—in this case, having no more than two types of fruits. We expand the window by adding elements from the right and contract it from the left when the condition is violated. This approach ensures we check all possible subarrays without starting from each element repeatedly, making it efficient.

This method works well because it continuously adjusts the window size based on the elements it encounters. By using a dictionary to keep track of the fruit counts within the window, we can efficiently manage and adjust the window size to find the maximum length subarray that satisfies the condition. The efficiency comes from the fact that each element is processed at most twice, once when added and once when removed from the window.

Step-by-Step Algorithm

• Initialize two variables: windowStart to keep track of the starting index of the window and maxLength to store the maximum length of the subarray found.
• Create a dictionary fruitFrequencyMap to count the frequency of each fruit in the current window.
• Iterate over the array using a variable windowEnd which marks the end of the window.
  • Add the current fruit at windowEnd to the dictionary and update its count.
  • If the dictionary size exceeds two, it means there are more than two types of fruits in the window.
    • Shrink the window from the start by removing the fruit at windowStart and updating the dictionary.
    • If the count of the fruit at windowStart becomes zero, remove it from the dictionary.
    • Move windowStart to the right to shrink the window.
  • Update maxLength to be the maximum of its current value and the size of the current window (windowEnd - windowStart + 1).
• Return maxLength as the result.

Algorithm Walkthrough

Consider the input array ['A', 'B', 'C', 'A', 'C']:

1. Initialize windowStart = 0, maxLength = 0, fruitFrequencyMap = {}.
2. windowEnd = 0: Add 'A' to fruitFrequencyMap, making it {'A': 1}.
3. windowEnd = 1: Add 'B' to fruitFrequencyMap, making it {'A': 1, 'B': 1}.
   • maxLength = 2 (subarray ['A', 'B']).
4. windowEnd = 2: Add 'C' to fruitFrequencyMap, making it {'A': 1, 'B': 1, 'C': 1}.
   • More than two types of fruits, shrink window: windowStart = 1, fruitFrequencyMap = {'A': 0, 'B': 1, 'C': 1}.
   • Remove 'A': fruitFrequencyMap = {'B': 1, 'C': 1}.
5. windowEnd = 3: Add 'A' to fruitFrequencyMap, making it {'B': 1, 'C': 1, 'A': 1}.
   • More than two types of fruits, shrink window: windowStart = 2, fruitFrequencyMap = {'B': 0, 'C': 1, 'A': 1}.
   • Remove 'B': fruitFrequencyMap = {'C': 1, 'A': 1}.
6. windowEnd = 4: Add 'C' to fruitFrequencyMap, making it {'C': 2, 'A': 1}.
   • maxLength = 3 (subarray ['C', 'A', 'C']).

Code

Here is what our algorithm will look like:

Complexity Analysis

Time Complexity:

• Single pass: The algorithm uses a sliding window approach, making a single pass through the input array. The outer loop runs once for each character in the input array, so it runs O(N) times, where N is the length of the array.

• Sliding window adjustment: The inner loop ensures that the window contains no more than two distinct characters. For each character, adding or removing from the fruitFrequencyMap takes constant time, O(1), because hash map operations (insertion, update, and deletion) are O(1) on average.

• The overall time complexity is O(N) because both the outer and inner loops process each element at most once.

Overall time complexity: O(N).

Space Complexity

• HashMap space: The fruitFrequencyMap stores the frequency of up to two distinct characters. The space complexity of the hash map is O(1), which is constant.

• Additional variables: The algorithm uses a few additional variables (windowStart, windowEnd, maxLength), which require constant space, O(1).

Overall space complexity: O(1).

Similar Problems

Problem 1: Longest Substring with at most 2 distinct characters

Given a string, find the length of the longest substring in it with at most two distinct characters.

Solution: This problem is exactly similar to our parent problem.