Count Subarrays Containing at Least k Disjoint Pairs of Equal Values

Fruits travel along a conveyor belt, and fruits[i] is the type of the i-th fruit, written as an integer. For a contiguous segment of the belt, a pair is two different positions in that segment that hold the same fruit type. A segment is good if you can choose at least k pairs from it such that no position belongs to more than one chosen pair.

Count the good segments.

Function Signature

def count_good_segments(fruits: list[int], k: int) -> int:

Rules

• A segment is fruits[l..r] with 0 <= l <= r < n, where n = len(fruits). Two segments are different when their (l, r) differ, even if their contents are equal.
• Chosen pairs must be disjoint: three fruits of one type in a segment allow only one pair, and four allow two.
• The two positions of a pair do not need to be adjacent.
• Return the total number of good segments, or 0 if there are none.

Constraints

• 1 <= n <= 10^5
• 1 <= fruits[i] <= 10^9
• 1 <= k <= 10^5
• The answer can be as large as n * (n + 1) / 2, which is 5,000,050,000 for n = 10^5 and exceeds 2^31 - 1; use a 64-bit integer in languages with fixed-width integers.

Examples

Example 1

Input: fruits = [3, 3, 3], k = 1
Output: 3

The good segments are [0..1], [1..2] and [0..2]; each contains at least one pair of 3s. Single fruits contain no pair.

Example 2

Input: fruits = [5, 1, 5, 1, 5], k = 2
Output: 3

The segments [0..3] and [1..4] each contain one pair of 5s and one pair of 1s, and [0..4] does as well. Every segment of length 3 or less contains at most one disjoint pair.

Example 3

Input: fruits = [1, 2, 3], k = 1
Output: 0

No fruit type appears twice.