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.

Count Belt Segments Holding k Disjoint Same-Type Pairs

Hints

1. For a fixed segment, work out how many disjoint pairs one fruit type contributes when it appears c times; pairs of different types never share a position.
2. Adding one more fruit to either end of a segment can never reduce the number of disjoint pairs you can choose.
3. Segments with equal contents but different (l, r) are counted separately, and the total can exceed 2^31 - 1.

Approach

In a segment, a type that appears c times contributes floor(c / 2) disjoint pairs, and pairs of different types never share a position, so the most disjoint pairs a segment [l..r] can hold is P(l, r) = sum over types of floor(c / 2). The segment is good exactly when P(l, r) >= k. Extending a segment never lowers any count, so P never decreases: if [l..r] is good, every [l'..r] with l' <= l is good too. Sweep r from left to right while keeping a hash map of type counts for the window [left..r] and the running value of P. Adding a fruit whose count becomes even raises P by one; removing a fruit whose count was even lowers P by one; odd transitions leave P unchanged. After adding fruits[r], advance left while the window is still good. Invariant: after processing r, every start l' < left gives a good segment ending at r (left moved past l' only when [l'..r'] was good for some r' <= r, and extending to r keeps it good), and [left..r] is not good, so no later start is good either. Exactly left good segments end at r, and the answer is the sum of left over all r. Each index enters and leaves the window at most once, so the sweep is linear. Edge cases: n = 1 or no repeated type gives 0; k larger than n / 2 gives 0 because no segment can hold that many disjoint pairs; three equal fruits give one pair and four give two; the total can reach n * (n + 1) / 2, above 2^31 - 1, so it is accumulated in a 64-bit integer (long in Java, long long in C++).

• Time complexity: O(n)
• Space complexity: O(n)