Strings Built From Blocks

Medium

Consider strings made of the characters 0 and 1. Split a string into blocks, the maximal runs of equal characters: for example, 0011101 splits into 00, 111, 0, 1. A string qualifies if: - its length is between shortest and longest inclusive; - the length of every block of ones is divisible by ones_step; - the length of every block of zeros is divisible by zeros_step. How many strings qualify? The count can be huge, so return it modulo 10⁹ + 7.

Example 1

shortest=3, longest=4, ones_step=2, zeros_step=1 → 8

Ones must come in blocks of even length, zeros in any length. Length 3: "000", "110", "011". Length 4: "0000", "1100", "0110", "0011", "1111". That is 8 in total.

Example 2

shortest=1, longest=5, ones_step=3, zeros_step=5 → 2

Only "111" and "00000" qualify: any other string contains a block of a forbidden length.

Example 3

shortest=2, longest=2, ones_step=1, zeros_step=1 → 4

Constraints

1 ≤ shortest ≤ longest ≤ 10⁵
1 ≤ ones_step, zeros_step ≤ longest

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

shortest=3, longest=4, ones_step=2, zeros_step=1

Expected

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