Festival Bookend Blocks

Count subarrays with equal ends and specified distinct count and max frequency

HardArrays & HashingSliding WindowInclusion-Exclusion

A film festival records its screenings in chronological order. The integer films[i] identifies the film shown at screening i; the same film may be shown multiple times.

The festival wants to designate contiguous, nonempty blocks of screenings as bookend blocks. A block qualifies when all three conditions hold:

  • Its first and last screenings show the same film. A single-screening block satisfies this condition.
  • It contains exactly distinct different film identifiers.
  • The largest number of screenings of any one film within the block is exactly peak. Multiple films may attain this number.

Return the number of qualifying blocks. Blocks with different starting or ending indices are counted separately, even if their sequences of film identifiers are identical.

Examples

Example 1

Input: films = [4,9,4,9,4], distinct = 2, peak = 2
Output: 3

The blocks at indices [0, 2], [1, 3], and [2, 4] each have matching bookends, contain exactly two films, and show their most frequent film twice. The full schedule does not qualify because film 4 appears three times.

Example 2

Input: films = [5,8,2,8,5], distinct = 3, peak = 2
Output: 1

Only the entire schedule has matching bookends, exactly three different films, and a largest film frequency of two.

Example 3

Input: films = [7,7,7], distinct = 1, peak = 1
Output: 3

Every single-screening block qualifies. Any longer block shows its only film more than once, so its largest frequency is not one.

Constraints

  • 0 <= films.length <= 14000
  • -10^9 <= films[i] <= 10^9
  • 1 <= distinct <= 14000
  • 1 <= peak <= 14000

The intended solution runs in O(n) time and O(n) auxiliary space. Film identifiers are labels; their numerical magnitudes do not affect eligibility. An empty schedule has no qualifying blocks.

Hints

Show hint 1

First count blocks with matching bookends, at most d different films, and every film frequency at most p. For a fixed right endpoint, valid starting positions form a suffix of the current window. How many of those positions contain the right endpoint's film?

Show hint 2

Use inclusion-exclusion on the two upper bounds to turn the at-most count into an exact distinct count and an exact largest frequency.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you adapt the counting method if the first and last films had to be different instead?
  • How would you count blocks whose number of different films and largest film frequency each lie within a supplied inclusive range?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem