Strings Built From Blocks

Medium

Start with an empty string and keep appending one of two blocks to its end: either zero_block copies of '0' in a row, or one_block copies of '1' in a row. The blocks can be mixed in any order. How many different strings with a length from min_len to max_len inclusive can be built this way? The number can be large, so return it modulo 10⁹ + 7.

Example 1

min_len=2, max_len=2, zero_block=1, one_block=1 → 4

Blocks are one character long and the length must be exactly 2: "00", "01", "10" and "11". The answer is 4.

Example 2

min_len=3, max_len=4, zero_block=2, one_block=3 → 2

Length 3 is reached only by "111", and length 4 only by "0000". The answer is 2.

Example 3

min_len=4, max_len=6, zero_block=1, one_block=2 → 26

Constraints

1 ≤ min_len ≤ max_len ≤ 10⁵
1 ≤ zero_block, one_block ≤ min_len

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Dynamic Programming

Similar problems

Longest Mirror Fragment Medium All Balanced Bracket Strings Medium Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium

Input

min_len=2, max_len=2, zero_block=1, one_block=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 43 tests on the server, hidden ones included.