Problem

Given two positive integers low and high represented as strings, find the count of stepping numbers in the inclusive range [low, high].

A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly 1.

Return an integer denoting the count of stepping numbers in the inclusive range [low, high].

Since the answer may be very large, return it modulo 10^9 + 7.

Note: A stepping number should not have a leading zero.

Examples

Example 1

1
2
3
4
5
6


    
    
    Input: low = "1", high = "11"
    Output: 10
    Explanation: The stepping numbers in the range [1,11] are 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10. There are a total of 10 stepping numbers in the range. Hence, the output is 10.

Example 2

1
2
3
4
5
6


    
    
    Input: low = "90", high = "101"
    Output: 2
    Explanation: The stepping numbers in the range [90,101] are 98 and 101. There are a total of 2 stepping numbers in the range. Hence, the output is 2.

Constraints

  • 1 <= int(low) <= int(high) < 10100
  • 1 <= low.length, high.length <= 100
  • low and high consist of only digits.
  • low and high don’t have any leading zeros.

Solution

Method 1 – Digit DP (Dynamic Programming on Strings)

Intuition

A stepping number is a number where every pair of adjacent digits differs by exactly 1. Since the numbers can be very large (up to 100 digits), we use digit DP to count stepping numbers up to a given bound. We count stepping numbers up to high, subtract those below low, and adjust for inclusivity.

Approach

  1. Define a DP function: dp(pos, prev, tight, leading_zero) where:
    • pos: current digit position
    • prev: previous digit (or -1 if none yet)
    • tight: whether the current prefix is equal to the bound’s prefix
    • leading_zero: whether we are still placing leading zeros
  2. For each position, try all possible digits:
    • If leading_zero, can start from 1 (no leading zeros allowed except for 0 itself).
    • If not leading_zero, the next digit must differ by 1 from prev.
    • If tight, the digit cannot exceed the corresponding digit in the bound.
  3. Base case: if all positions are filled, return 1 if not leading_zero, else 0.
  4. Memoize the DP function.
  5. To count in [low, high], compute f(high) - f(low-1), where f(x) is the count of stepping numbers ≤ x.
  6. For low-1, implement a helper to subtract 1 from a string number.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    static final int MOD = 1_000_000_007;
    public int countSteppingNumbers(String low, String high) {
        return (int)((f(high) - f(dec(low)) + MOD) % MOD);
    }
    private int f(String s) {
        Integer[][][] dp = new Integer[s.length()+1][11][2];
        return dfs(0, 10, 1, 1, s, dp);
    }
    private int dfs(int pos, int prev, int tight, int leadingZero, String s, Integer[][][] dp) {
        if (pos == s.length()) return leadingZero == 0 ? 1 : 0;
        if (dp[pos][prev][tight] != null) return dp[pos][prev][tight];
        int res = 0, up = tight == 1 ? s.charAt(pos) - '0' : 9;
        for (int d = 0; d <= up; d++) {
            if (leadingZero == 1 && d == 0) {
                res = (res + dfs(pos+1, 10, tight & (d == up ? 1 : 0), 1, s, dp)) % MOD;
            } else if (prev == 10 || Math.abs(d - prev) == 1) {
                res = (res + dfs(pos+1, d, tight & (d == up ? 1 : 0), 0, s, dp)) % MOD;
            }
        }
        return dp[pos][prev][tight] = res;
    }
    private String dec(String s) {
        char[] arr = s.toCharArray();
        int i = arr.length - 1;
        while (i >= 0 && arr[i] == '0') arr[i--] = '9';
        if (i >= 0) arr[i]--;
        int j = 0; while (j < arr.length && arr[j] == '0') j++;
        return j == arr.length ? "0" : new String(arr, j, arr.length - j);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def countSteppingNumbers(self, low: str, high: str) -> int:
        MOD = 10**9 + 7
        from functools import lru_cache
        def dec(s: str) -> str:
            arr = list(s)
            i = len(arr) - 1
            while i >= 0 and arr[i] == '0':
                arr[i] = '9'
                i -= 1
            if i >= 0:
                arr[i] = str(int(arr[i]) - 1)
            j = 0
            while j < len(arr) and arr[j] == '0':
                j += 1
            return '0' if j == len(arr) else ''.join(arr[j:])
        def f(s: str) -> int:
            @lru_cache(None)
            def dp(pos: int, prev: int, tight: bool, leading_zero: bool) -> int:
                if pos == len(s):
                    return 0 if leading_zero else 1
                res = 0
                up = int(s[pos]) if tight else 9
                for d in range(0, up+1):
                    if leading_zero and d == 0:
                        res = (res + dp(pos+1, 10, tight and d == up, True)) % MOD
                    elif prev == 10 or abs(d - prev) == 1:
                        res = (res + dp(pos+1, d, tight and d == up, False)) % MOD
                return res
            return dp(0, 10, True, True)
        return (f(high) - f(dec(low)) + MOD) % MOD

Complexity

  • ⏰ Time complexity: O(L * 11 * 2 * 2), where L is the number of digits (up to 100), for each position, previous digit, tight, and leading_zero state.
  • 🧺 Space complexity: O(L * 11 * 2 * 2), for the DP memoization table.