Show problems as
Classic problem #2466MediumDynamic Programming

Count Ways To Build Good Strings

Real-world version: Counting Jingle Playlists
Tracked in this browser only
Read Count Ways To Build Good Strings on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard 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)

More on the same topics