Loading page…
Practice problem · hard
Kestrel Stream tags every play with a content category, such as news, comedy or ambient music. Categories are stored as numbers.
The analytics team studies how listeners move between kinds of content. They define a session as one or more consecutive plays in a listener's history. A session touches a category when at least one of its plays has that category.
To tune the mix of recommendations, the team wants a count: how many sessions in one history touch exactly k categories. Two sessions are different when they start or end at different plays. A long history holds billions of sessions.
Write count_exact_sessions(categories, k).
categories[i] is the category of play i in the listener's history, in order.i to position j with i ≤ j.k different categories.k is larger than the number of different categories in the whole history, return 0.Input: categories = [2, 1, 2, 3, 3], k = 2
Output: 5Count the sessions with at most 2 categories, then those with at most 1. At each right, every start from left to right is a valid session, so each pass adds right - left + 1.
| right | Category | At most 2: left | Adds | At most 1: left | Adds | Exactly 2 ending here |
|---|---|---|---|---|---|---|
| 0 | 2 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 2 | 1 | 1 | 1 |
| 2 | 2 | 0 | 3 | 2 | 1 | 2 |
| 3 | 3 | 2 | 2 | 3 | 1 | 1 |
| 4 | 3 | 2 | 3 | 3 | 2 | 1 |
| Total | 11 | 6 | 5 |
The five sessions are 2, 1, 2, 1, 2, 1, 2, 2, 3 and 2, 3, 3.
Input: categories = [4, 4, 5], k = 3
Output: 0The whole history has only two categories, so no session has three.
Input: categories = [7, 7, 7, 2, 2], k = 1
Output: 9With k = 1, every session inside a run of one category counts: 6 in the run of three 7s and 3 in the run of two 2s.
1 ≤ categories.length ≤ 10^5 (about 278 days of plays at 4 minutes a track)1 ≤ categories[i] ≤ 10001 ≤ k ≤ 1000A history of n plays has n(n + 1) / 2 sessions: 5,000,050,000 at n = 10^5. Checking each one is far over the budget of about 10^8 simple operations a second, so aim for O(n).
The answer itself can be that large. It is more than 2^31 − 1 = 2,147,483,647, so use long in Java and long long in C++.
count_exact_sessions · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.