1268. Uniform Spread Stretches
A bakery logs the flavour code of each tray it bakes, in order, in the array nums. Let menu be the set of all distinct flavour codes that appear anywhere in the log. A contiguous stretch of the log has a uniform spread when every flavour on the menu appears in it, and each of them appears exactly the same number of times.
Return the number of non-empty stretches with a uniform spread. If the menu has a single flavour, every non-empty stretch qualifies. Stretches at different positions count separately. The answer can exceed 32 bits, so return it as a 64-bit integer.
Aim for O(n) expected time and O(n) extra space: the stretches between two prefixes qualify exactly when the prefixes differ by the same amount in every flavour.
Example 1
- Input:
- nums = [8,3,8,5,3,5,5,8,3]
- Output:
- 5
- Explanation:
The menu is 8, 3 and 5, and five stretches (rows 0 to 5, 0 to 8, 1 to 3, 2 to 4, 6 to 8) hold all three with equal counts.
Example 2
- Input:
- nums = [12,40,12,40,40,12,7]
- Output:
- 1
- Explanation:
The menu is 12, 40 and 7, and only the stretch 40,12,7 contains the lone 7 with equal counts, so the answer is 1.
Example 3
- Input:
- nums = [9,4,9,9,4,6,4,6,9,6]
- Output:
- 5
- Explanation:
The menu is 9, 4 and 6, and five stretches hold all three flavours with equal counts, such as rows 1 to 9 with three of each.
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)