747. Building Good Strings
A signalling lamp builds messages out of two kinds of pulses. A dim pulse adds exactly zero copies of the character '0' to the end of the message, and a bright pulse adds exactly one copies of '1'. A message starts empty and may receive any number of pulses, each of either kind.
A message is good if its final length is between low and high inclusive. Count the distinct good messages. The count can be huge, so return it modulo 1000000007.
Aim for time O(high) and space O(high).
Example 1
- Input:
- low = 4high = 6zero = 2one = 3
- Output:
- 5
- Explanation:
Length 4 has 1 message (two dim pulses), length 5 has 2 (dim+bright in either order), length 6 has 2 (three dims or two brights): 5 in total.
Example 2
- Input:
- low = 3high = 3zero = 2one = 2
- Output:
- 0
- Explanation:
Every pulse adds 2 characters, so a message of length 3 cannot exist and the answer is 0.
Example 3
- Input:
- low = 1high = 3zero = 1one = 1
- Output:
- 14
- Explanation:
Each step appends one character, either 0 or 1, giving 2 + 4 + 8 = 14 messages of length 1 to 3.
Constraints
1 ≤ low ≤ high ≤ 105
1 ≤ zero, one ≤ high
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(high)
- Space
- O(high)