Count Binary Strings Built from Fixed Zero and One Blocks
Company: Visa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Start with an empty string. In each operation, append either a block of `zero` copies of `'0'` or a block of `one` copies of `'1'`. The parameters `zero` and `one` are positive block lengths. Return the number of different strings you can build with length from `low` through `high`, inclusive, modulo `10^9 + 7`.
```cpp
class Solution {
public:
int countGoodStrings(int low, int high, int zero, int one);
};
```
### Examples
**Example 1:**
```text
Input: low = 2, high = 2, zero = 1, one = 1
Output: 4
Explanation: The four strings are "00", "01", "10", and "11".
```
**Example 2:**
```text
Input: low = 3, high = 3, zero = 1, one = 2
Output: 3
Explanation: The valid strings are "000", "011", and "110".
```
### Constraints
- `1 <= low <= high <= 100000`.
- `1 <= zero, one <= low`.
### Clarifying Questions
- Can the two block lengths be equal? Yes; the appended characters still differ.
- Can blocks be appended in any order? Yes.
- Does the empty string count? No; `low >= 1`.
- Are the length bounds inclusive? Yes.
```hint Check the boundary
If the block lengths are equal, check whether choosing zeroes and choosing ones produce the same string.
```
Overview: Count distinct binary strings built by appending fixed-length zero blocks or one blocks, within an inclusive range of lengths.