1260. Paired-Up Stretches
A telemetry team stores one event code per row of a log. A contiguous stretch of rows is paired-up when every distinct code inside it occurs an even number of times: the codes 7, 3, 3, 7 form a paired-up stretch, while 7, 3, 7 does not.
Given the array nums, return how many non-empty contiguous stretches are paired-up. Stretches at different positions count separately even when they hold the same codes. The total can exceed 32 bits, so return it as a 64-bit integer.
Checking every stretch is too slow for 100,000 rows. Aim for O(n) expected time and O(n) extra space by summarising each prefix of the log with a single compact signature.
Example 1
- Input:
- nums = [7,12,7,9,9,12,4,4]
- Output:
- 4
- Explanation:
The paired-up stretches are rows 0 to 5, rows 0 to 7, rows 3 to 4 and rows 6 to 7, so 4 in total.
Example 2
- Input:
- nums = [31,5,5,31,8,2,8,2,5]
- Output:
- 4
- Explanation:
The paired-up stretches are rows 0 to 3, rows 0 to 7, rows 1 to 2 and rows 4 to 7, so 4 in total.
Example 3
- Input:
- nums = [64,9,9,64,17,23,17,40]
- Output:
- 2
- Explanation:
Only rows 0 to 3 and rows 1 to 2 have every code an even number of times, so the answer is 2.
Constraints
1 ≤ n ≤ 105
1 ≤ nums[i] ≤ 109
The answer fits in a 64-bit integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)