Restore the Array — Hard Problem & Solution

A program printed an array of integers, each between 1 and k inclusive, and lost the separators — leaving only the digit string s.

Difficulty: Hard
Topics: Strings, Dynamic Programming
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A program printed an array of integers, each between 1 and k inclusive, and lost the separators — leaving only the digit string s.

Return how many arrays could have produced s, modulo 10⁹ + 7. No printed integer had a leading zero.

Example 1

Input: s = "1000", k = 10000
Output: 1
Explanation: Only `[1000]`; `[1, 000]` is invalid because of the leading zeros.

Example 2

Input: s = "1000", k = 10
Output: 0
Explanation: No split avoids a number above 10 or a leading zero.

Example 3

Input: s = "1317", k = 2000
Output: 8

Constraints

1 <= s.length <= 10^5
s consists of only digits and does not contain leading zeros.
1 <= k <= 10^9

How to solve Restore the Array

Suffix DP. dp[i] counts the splits of s[i..], with dp[n] = 1. If s[i] is '0' the suffix is unsplittable. Otherwise extend a number rightwards from i, adding dp[j+1] for each prefix that stays within k.

Approach

Set dp[n] = 1.
Work i down from n-1. Return 0 immediately for s[i] == '0'.
Build num = num * 10 + digit for j from i upward, breaking once num > k.
Accumulate dp[j+1] modulo 10⁹ + 7.

Why it works

The inner loop is bounded by the digit count of k — at most ten steps — because any longer number exceeds k and breaks out, which is what keeps the whole thing linear despite looking quadratic. The running num must be held in 64 bits: one digit past k it can reach about ten billion before the comparison stops it.

Complexity

Time — O(n · log₁₀ k)
Space — O(n)

Pitfalls

A number may not start with '0', but zeros inside a number are fine.
num overflows 32 bits on the digit that trips the > k check.
dp[n] = 1 — the empty suffix has exactly one (trivial) split.

Reference solution

Python

def numberOfArrays(s: str, k: int) -> int:
    MOD = 10**9 + 7
    n = len(s)
    dp = [0] * (n + 1)
    dp[n] = 1
    for i in range(n - 1, -1, -1):
        if s[i] == "0":
            dp[i] = 0
            continue
        num = 0
        total = 0
        for j in range(i, n):
            num = num * 10 + int(s[j])
            if num > k:
                break
            total = (total + dp[j + 1]) % MOD
        dp[i] = total
    return dp[0]

JavaScript

var numberOfArrays = function(s, k) {
    var MOD = 1000000007;
    var n = s.length;
    var dp = [];
    for (var t = 0; t <= n; t++) dp.push(0);
    dp[n] = 1;
    for (var i = n - 1; i >= 0; i--) {
        if (s.charAt(i) === "0") { dp[i] = 0; continue; }
        var num = 0, total = 0;
        for (var j = i; j < n; j++) {
            num = num * 10 + (s.charCodeAt(j) - 48);
            if (num > k) break;
            total = (total + dp[j + 1]) % MOD;
        }
        dp[i] = total;
    }
    return dp[0];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue