Count Stepping Numbers Between Two String Bounds
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Count Stepping Numbers Between Two String Bounds
You are given positive integers `low` and `high` as decimal strings. Count the stepping numbers in the inclusive range `[low, high]`.
A stepping number has an absolute difference of exactly `1` between every pair of adjacent digits. It must not have a leading zero. Return the count modulo `10^9 + 7`.
### Examples
**Example 1**
```text
Input: low = "20", high = "35"
Output: 4
```
The qualifying numbers are `21`, `23`, `32`, and `34`. Each adjacent digit difference is exactly one.
**Example 2**
```text
Input: low = "100", high = "123"
Output: 3
```
The qualifying numbers are `101`, `121`, and `123`. A zero may appear after the first digit, as in `101`; adjacent equal digits, as in `100` or `122`, do not satisfy the condition.
### Constraints
- `1 <= int(low) <= int(high) < 10^100`.
- `1 <= low.length, high.length <= 100`.
- `low` and `high` contain only digits.
- Neither input string has leading zeros.
Here `int(low)` and `int(high)` describe their mathematical integer values; the inputs may be too large for fixed-width integer types.
### Clarifying Questions
- Are both endpoints included? Yes; count either endpoint if it is a stepping number.
- Do single-digit positive numbers qualify? Yes; they have no adjacent digit pair that violates the rule.
- Is a difference of zero or two allowed? No; the absolute difference must be exactly one.
- Are zeros forbidden everywhere? Only a leading zero is forbidden; internal zeros may be valid.
- Is zero part of the requested range? No; the lower bound is at least one.
### C++ Interface
```cpp
class Solution {
public:
int countSteppingNumbers(string low, string high) {
}
};
```
### Reasoning Checkpoints
- Retain the inclusive lower boundary as well as the upper boundary.
- Handle the full string length without converting the bounds to machine integers.
- Distinguish a number's real digits from any representation used to handle shorter numbers.
```hint Prefix choices
While choosing digits from left to right under an upper bound, what information determines which next digits remain legal?
```
Overview: Count positive integers in an inclusive string-bounded range whose neighboring decimal digits differ by exactly one, returning the count modulo one billion and seven.
