---

Условие задачи

Дан массив ASCII-символов, в котором каждый символ обозначает вид фруктового дерева. У вас есть две корзины, и в каждую можно складывать фрукты только одного вида.

Можно начать с любого дерева, но после начала нельзя пропускать деревья. Сбор заканчивается перед первым деревом третьего вида. Найдите максимальное количество фруктов, которое можно собрать в две корзины.

Пример 1:

Вход: ['A', 'B', 'C', 'A', 'C']
Выход: 3
Пояснение: на участке ['C', 'A', 'C'] можно собрать два фрукта C и один фрукт A.

Пример 2:

Вход: ['A', 'B', 'C', 'B', 'B', 'C']
Выход: 5
Пояснение: на участке ['B', 'C', 'B', 'B', 'C'] можно собрать три фрукта B и два фрукта C.

Решение

Задача сводится к поиску самого длинного непрерывного подмассива, содержащего не более двух различных видов фруктов. Это частный случай задачи о самой длинной подстроке с k различными символами при k=2.

Расширяем окно вправо и учитываем частоту каждого вида. Если в окне оказалось больше двух видов, сдвигаем левую границу, пока видов снова не станет не больше двух. После этого обновляем максимальную длину.

Код

package main

import "fmt"

func fruitsIntoBaskets(fruits []byte) int {
	frequencies := make(map[byte]int)
	windowStart := 0
	maxFruits := 0

	for windowEnd, fruit := range fruits {
		frequencies[fruit]++

		for len(frequencies) > 2 {
			leftFruit := fruits[windowStart]
			frequencies[leftFruit]--
			if frequencies[leftFruit] == 0 {
				delete(frequencies, leftFruit)
			}
			windowStart++
		}

		windowLength := windowEnd - windowStart + 1
		if windowLength > maxFruits {
			maxFruits = windowLength
		}
	}

	return maxFruits
}

func main() {
	fmt.Println("Максимальное количество фруктов:", fruitsIntoBaskets([]byte{'A', 'B', 'C', 'A', 'C'}))
	fmt.Println("Максимальное количество фруктов:", fruitsIntoBaskets([]byte{'A', 'B', 'C', 'B', 'B', 'C'}))
}

Вывод:

Максимальное количество фруктов: 3
Максимальное количество фруктов: 5

Временная сложность

Каждый элемент добавляется в окно и удаляется из него не более одного раза, поэтому временная сложность равна \(O(N)\).

Пространственная сложность

В частотной таблице одновременно находится не более трёх видов фруктов, поэтому алгоритм использует \(O(1)\) дополнительной памяти.

---