Narrative Pair Subarrays
MediumSliding Window · Meta
A story is a list of scene ids values. A section is any contiguous, non-empty subarray values[l..r].
A section's repetition score is the number of index pairs (i, j) with l <= i < j <= r and values[i] == values[j]. For example, a section containing the same id three times contributes 3 pairs for that id.
Given values and an integer k, return how many sections have a repetition score of at least k.
Example 1
- Input:
- values = [2, 1, 2, 1, 2], k = 2
- Output:
- 3
- Explanation
[2, 1, 2, 1]and[1, 2, 1, 2]each have one pair of 2s and one pair of 1s, for a score of 2. The whole list has three pairs of 2s plus one pair of 1s. Every shorter section has at most one pair, so the answer is 3.
Example 2
- Input:
- values = [5, 5, 5], k = 1
- Output:
- 3
- Explanation
- Both length-2 sections are a single pair, and the full section has 3 pairs, so 3 sections qualify.
Example 3
- Input:
- values = [1, 2, 3, 4], k = 1
- Output:
- 0
- Explanation
- All ids are different, so no section has any pair.
Constraints
1 <= values.length <= 10^51 <= values[i] <= 10^91 <= k <= 10^9- The answer fits in a 64-bit integer