Restore the Array

Hard
1061.

Restore the Array

Restore the Array is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var numberOfArrays = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Restore the Array — Solution in Python, Java & C++

Restore the Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Restore the Array is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Microsoft interviews.

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

Hints for Restore the Array

  1. Hint 1

    dp[i] = the number of ways to split the suffix starting at i.

  2. Hint 2

    A suffix beginning with '0' has no valid split at all.

  3. Hint 3

    Otherwise grow a number digit by digit and stop as soon as it exceeds k.

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

  1. Set dp[n] = 1.
  2. Work i down from n-1. Return 0 immediately for s[i] == '0'.
  3. Build num = num * 10 + digit for j from i upward, breaking once num > k.
  4. 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]

Java

public static int numberOfArrays(String s, int k) {
    final long MOD = 1000000007L;
    int n = s.length();
    long[] dp = new long[n + 1];
    dp[n] = 1;
    for (int i = n - 1; i >= 0; i--) {
        if (s.charAt(i) == '0') {
            dp[i] = 0;
            continue;
        }
        long num = 0, total = 0;
        for (int j = i; j < n; j++) {
            num = num * 10 + (s.charAt(j) - '0');
            if (num > k) break;
            total = (total + dp[j + 1]) % MOD;
        }
        dp[i] = total;
    }
    return (int) dp[0];
}

C++

int numberOfArrays(string s, int k) {
    const long long MOD = 1000000007LL;
    int n = (int) s.size();
    vector<long long> dp(n + 1, 0);
    dp[n] = 1;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '0') {
            dp[i] = 0;
            continue;
        }
        long long num = 0, total = 0;
        for (int j = i; j < n; j++) {
            num = num * 10 + (s[j] - '0');
            if (num > k) break;
            total = (total + dp[j + 1]) % MOD;
        }
        dp[i] = total;
    }
    return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming