Count Subarrays Containing at Least k Disjoint Pairs of Equal Values
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
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
```python
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**
```text
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**
```text
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**
```text
Input: fruits = [1, 2, 3], k = 1
Output: 0
```
No fruit type appears twice.
Overview: Count the contiguous segments of an integer array, framed as fruit types on a conveyor belt, that contain at least k pairs of equal values with no position used in two pairs. Tests reasoning about how the number of disjoint pairs changes as a segment grows, and efficient counting on inputs of up to 100,000 elements.
Fruits travel along a conveyor belt. You are given an integer array `fruits`, where `fruits[i]` is the type of the i-th fruit, and an integer `k`.
A segment is a contiguous part of the belt, `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.
Within a segment, a pair is two different positions that hold the same fruit type. The two positions of a pair do not need to be adjacent. 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. Because chosen pairs must be disjoint, three fruits of one type in a segment allow only one pair, and four allow two.
Return the total number of good segments, or `0` if there are none.
**Example 1**
```text
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. A single fruit contains no pair.
**Example 2**
```text
Input: fruits = [5, 1, 5, 1, 5], k = 2
Output: 3
```
The segments `[0..3]`, `[1..4]` and `[0..4]` each contain one pair of 5s and one pair of 1s. Every segment of length 3 or less contains at most one disjoint pair.
**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`; return it as a 64-bit integer (`long` in Java, `long long` in C++).
Constraints
- 1 <= n <= 10^5, where n = len(fruits)
- 1 <= fruits[i] <= 10^9
- 1 <= k <= 10^5
- The answer can be as large as n * (n + 1) / 2 (5,000,050,000 for n = 10^5), which exceeds 2^31 - 1: return a 64-bit integer (long in Java, long long in C++)
Examples
Input: ([7], 1)
Expected Output: 0
Explanation: A single fruit holds no pair.
Input: ([4, 4], 1)
Expected Output: 1
Explanation: Only the full two-fruit segment holds a pair.
Hints
- 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.
- Adding one more fruit to either end of a segment can never reduce the number of disjoint pairs you can choose.
- Segments with equal contents but different (l, r) are counted separately, and the total can exceed 2^31 - 1.