0668MediumDynamic Programming

Counting Jingle Playlists

Tracked in this browser only

Trains the technique from

LeetCode 2466Count Ways To Build Good Strings

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A radio station fills its breaks with jingles. Two jingles are on file: a chime that runs for chime seconds and a fanfare that runs for fanfare seconds. A playlist is a sequence of jingles played back to back with no gap between them, so the length of a playlist in seconds is the total of the lengths of the jingles in it. Either jingle may be used as often as the producer likes, or not at all.

A playlist may go to air when its length is at least low seconds and at most high seconds.

Two playlists are different when they hold a different number of jingles, or when at some position one plays the chime and the other plays the fanfare. So if the chime and the fanfare happen to run for the same number of seconds, chime-then-fanfare and fanfare-then-chime are still two different playlists.

Return the number of different playlists that may go to air. The count can be enormous, so return it modulo 1000000007.

Examples

Example 1

Input: low = 6, high = 8, chime = 2, fanfare = 3
Output: 9

Nine playlists run for six, seven or eight seconds. At six seconds: three chimes, or two fanfares. At seven: the fanfare in any one of three positions among two chimes. At eight: four chimes, or two fanfares plus one chime with the chime in any of three positions.

Example 2

Input: low = 10, high = 10, chime = 3, fanfare = 7
Output: 2

Ten seconds can only be filled by one chime and one fanfare, and the two of them can be played in either order.

Example 3

Input: low = 5, high = 5, chime = 5, fanfare = 5
Output: 2

A single jingle fills the five seconds, and the chime and the fanfare count as different playlists even though they run for the same time.

Constraints

1 <= low <= high <= 10^5
1 <= chime, fanfare <= low
The count is returned modulo 1000000007.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_playlists(low: int, high: int, chime: int, fanfare: int) -> int:

Java

public int countPlaylists(int low, int high, int chime, int fanfare)

The intended approach

Time O(high): one pass over the lengths.Space O(high) for the tally per length.

Count playlists by length. A playlist of length `d` seconds ends with either a chime or a fanfare, and dropping that last jingle leaves a playlist of length `d - chime` or `d - fanfare`, so the tally for `d` is the sum of the tallies for those two shorter lengths, with the empty playlist seeded at length `0`. Fill the tallies from `1` up to `high`, reducing each modulo the given number, and add in the tallies for lengths from `low` upwards as they are computed.

Pythonentry point: count_playlists

def count_playlists(low, high, chime, fanfare):
    MOD = 1000000007
    # ways[d] = playlists lasting exactly d seconds; each ends with a chime or a fanfare
    ways = [0] * (high + 1)
    ways[0] = 1
    total = 0
    for d in range(1, high + 1):
        cur = 0
        if d >= chime:
            cur += ways[d - chime]
        if d >= fanfare:
            cur += ways[d - fanfare]
        ways[d] = cur % MOD
        if d >= low:
            total = (total + ways[d]) % MOD
    return total

The obvious version

Group playlists by how many chimes and how many fanfares they hold. A playlist with `a` chimes and `b` fanfares has a fixed length, and the number of such playlists is the number of ways to choose which `a` of the `a + b` positions carry the chime. Walk every pair whose length is within the window, add that binomial coefficient in exact integers, and reduce once at the end.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_playlists(low, high, chime, fanfare):
    from math import comb
    total = 0
    a = 0
    while a * chime <= high:
        b = 0
        while a * chime + b * fanfare <= high:
            span = a * chime + b * fanfare
            if a + b > 0 and low <= span <= high:
                total += comb(a + b, a)
            b += 1
        a += 1
    return total % 1000000007

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in